| Summary: | It is impossible to effectively modify a string in order to increase its Kolmogorov complexity. However, is it possible to construct a few strings, no longer than the input string, so that most of them have larger complexity? We show that the answer is yes. We present an algorithm that takes as input a string <i>x</i> of length <i>n</i> and returns a list with <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>O</mi><mo>(</mo><msup><mi>n</mi><mn>2</mn></msup><mo>)</mo></mrow></semantics></math></inline-formula> strings, all of length <i>n</i>, such that 99% of them are more complex than <i>x</i>, provided the complexity of <i>x</i> is less than <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>−</mo><mo form="prefix">log</mo><mo form="prefix">log</mo><mi>n</mi><mo>−</mo><mi>O</mi><mo>(</mo><mn>1</mn><mo>)</mo></mrow></semantics></math></inline-formula>. We also present an algorithm that obtains a list of quasi-polynomial size in which each element can be produced in polynomial time.
|
|---|