Name
Abstract | ||
|---|---|---|
How much do we have to change a string to increase its Kolmogorov complexity? We show that we can increase the complexity of any non-random string of length n by flipping $O(\sqrt{n})$ bits and some strings require $\Omega(\sqrt{n})$ bit flips. For a given m, we also give bounds for increasing the complexity of a string by flipping m bits. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1007/978-3-540-31856-9_34 | Symposium on Theoretical Aspects of Computer Science |
Keywords | Field | DocType |
m bit,length n,kolmogorov complexity,non-random string | Discrete mathematics,Combinatorics,Kolmogorov complexity,Omega,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
3404 | 081 | 0302-9743 |
ISBN | Citations | PageRank |
3-540-24998-2 | 6 | 0.50 |
References | Authors | |
2 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Harry Buhrman | 1 | 1607 | 117.99 |
| Lance Fortnow | 2 | 2788 | 352.32 |
| Ilan Newman | 3 | 1149 | 82.18 |
| Nikolai K. Vereshchagin | 4 | 193 | 25.19 |