Incompressibility Method For Proving Time Complexity Lower Bounds

The incompressibility method is a technique in computational complexity theory for proving lower bounds on the time complexity of computational problems. The key idea is to use randomly generated strings that are incompressible to force any algorithm to store or transmit a certain amount of information, which requires a minimum number of steps.

The Concept of Incompressibility

An incompressible string is a string that cannot be represented in a more compact form without loss of information. More formally, a string x is incompressible by k bits if its Kolmogorov complexity is at least |x| – k. The Kolmogorov complexity of a string is the length of the shortest program that can output the string.

Incompressible strings exhibit high randomness and entropy. They contain no recognizable patterns or regularities that allow for data compression. As a result, the entire string has to be stored or transmitted bit-for-bit by an algorithm or communication protocol.

Generating Incompressible Strings

Truly random strings generated by fair coin flips have high Kolmogorov complexity with overwhelming probability. However, it is difficult to formally prove the incompressibility of physical random sources.

Instead, incompressible strings can be generated using pseudorandom generators based on number-theoretic assumptions, block ciphers, or cryptographic hash functions. The security proofs for these primitives can demonstrate incompressibility with high probability.

Using Incompressibility in Proofs

The key insight is that any algorithm or protocol that processes incompressible input strings must store or transmit the entire input due to its randomness. This allows setting a lower bound on the number of steps required based on input length times algorithmic operations.

By carefully constructing an adversarial input distribution consisting of incompressible strings, lower bounds can be proven even for average-case complexity rather than just worst-case.

Using Incompressible Strings to Prove Time Lower Bounds

Incompressible input strings can be used to prove lower bounds on the time complexity of problems in multiple computational models, including comparison-based algorithms, Turing machines, circuits, communication protocols, and data stream algorithms.

Example: Lower Bound for Comparison Sorting

As an illustrative example, we can use incompressible strings to prove an Ω(n log n) lower bound on the number of comparisons required to sort n distinct elements using any comparison-based algorithm.

We construct an input distribution where each of the n inputs is an incompressible string from {0, 1}ⁿ. To properly order these strings, the sorting algorithm must somehow encode the relative order between each pair of strings using its comparison operators. With n strings, there are Θ(n²) such pairs.

Each comparison reveals at most 1 bit of information about the relative order. To have enough information to fully order all pairs, the number of comparison operations must be at least Ω(n²). Using information-theoretic arguments, this can be tightened to Ω(n log n) comparisons even for random input strings.

Since the strings are incompressible, the algorithm cannot take any shortcuts – every bit of information must come from a comparison. This proves an asymptotic lower bound on the problem itself.

Other Examples

Similar arguments using carefully constructed incompressible input distributions have been used to prove lower bounds for integer sorting, string matching, formula and circuit evaluation, and other problems across various computational models.

Often the bounds match known algorithmic upper bounds, establishing the problem’s intrinsic difficulty and showing that known solutions are asymptotically optimal.

Relation to Kolmogorov Complexity

The theory of computational complexity relies heavily on Kolmogorov complexity. The incompressibility method can be seen as an application of Kolmogorov complexity to prove lower bounds on time complexity.

Kolmogorov Complexity

The Kolmogorov complexity K(x) of a string x is the length of the shortest binary program P that prints x and halts. It quantifies the absolute information content of the string.

A string is incompressible by k bits if its Kolmogorov complexity is at least |x| – k. Such a string contains close to maximum entropy and information density.

Applications to Complexity Theory

Kolmogorov complexity provides a fundamental basis for classifying computational problems based on information content. It helps distinguish between polynomial vs exponential complexity classes.

The time to run program P serves as an absolute lower bound for the runtime required to generate or process string x. This connection enables proofs based on incompressible inputs.

While Kolmogorov complexity is non-computable, compressibility arguments remain valid when implemented with concrete complexity-theoretic primitives like one-way functions.

Applications in Communication Complexity

The information-theoretic paradigm extends beyond time complexity to models like communication complexity that analyze information transfer. Incompressibility arguments are often easier for communication protocols.

Communication Complexity

Communication complexity examines the minimum amount of information that must be communicated to solve distributed problems with inputs divided among multiple parties.

It has applications in VLSI circuit design, limited-bandwidth streaming, secure multi-party computation, and data structures for distributed systems.

Lower Bounds from Incompressibility

Incompressibility arguments are straightforward for communication protocols – the entire input must be transmitted across at least one cut that partitions the inputs. This directly yields lower bounds based on input size.

Randomized protocols require more intricate constructions involving distributions where each input occurs with an incompressible hash code appended, in order to prove distributional communication complexity lower bounds.

Quantum communication complexity also relies heavily on incompressibility methods because quantum information itself cannot be compressed.

Open Problems with the Incompressibility Method

While the incompressibility method has been remarkably successful in proving tight lower bounds across computational models, many open problems remain.

P vs NP Problem

No progress has been made on resolving the P vs NP question for general Boolean circuits. Incompressibility arguments work well for restricted circuit classes but obtaining lower bounds for general circuits remains elusive.

Parallel and Quantum Algorithms

For parallel algorithms and quantum algorithms, far fewer lower bounds via incompressibility are known. Expanding this method could shed light on the capabilities and limitations of massively parallel computing.

Stronger Incompressibility Notions

Alternative formalizations of randomness such as multi-source extractors strengthen incompressibility guarantees but are harder to apply towards proving lower bounds. Relating these notions to computational complexity is an active research direction.