Kolmogorov complexity and computational complexity

Authors

Publication date 23 January 1993

Computational complexity computational complexity theory Kolmogorov complexity oracle complexity resource-bounded programs

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Proceedings, conferences, collections, etc. pertaining to computer science (68-06) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

[The articles of this volume will not be indexed individually.] This book gives a reasonably comprehensive picture of how Kolmogorov complexity (and its modifications) are applied to computational complexity theory. Kolmogorov complexity \(K(x)\) of a word \(x\) is, crudely speaking, the smallest length of a program that generates \(x\). For some words \(x\), these shortest programs are non-feasible (e.g., require too long a time), so it is natural to restrict ourselves to resource-bounded programs, i.e., programs whose time, or space, or some other characteristic is limited by \(f(\ell(x))\), where \(f\) is a given function, and \(\ell(x)\) is the length of a word \(x\); then, we can define complexity \(K_ b(x)\) as the smallest length of a resource-bounded program that generates \(x\). In the first paper (by \textit{E. Allender}), time-bounded Kolmogorov complexity turns out to be related to the question of whether NEXP (i.e., the class of all problem solvable by a non-deterministic exponentialtime algorithm) is equal to EXP. Namely, this question can be reformulated in terms of the asymptotic behavior of time-bounded \(K_ b(x)\). This reformulation (and several similar ones) help in solving several problems about oracle complexity (with respect to random and generic oracles), circuit complexity, etc. Another relationship between \(K_ b(x)\) and oracles is described in a paper by \textit{R. V. Book}. It is known that for some oracles \(A\), \(NP^ A=P^ A\), while for some others \(NP^ A\neq P^ A\). Since we are interested in the \(NP=?P\) problem, it is desirable to find out what oracles are suitable for that purpose, i.e., for what \(A\) we can deduce \(NP\neq P\) from \(NP^ A\neq P^ A\). Initially, it was conjectured that this is true for random \(A\). But later on, it turned out that some properties that are true for almost all oracles \(A\) (and hence for all random oracles), are not true for computations without an oracles \(A\) (and hence for all randomoracles), are not true for computations without an oracle. So, if an oracle \(A\) is random (i.e., crudely speaking, has the biggest Kolmogorov complexity), then \(A\) is not suitable for proving that \(NP\neq P\). The natural text hypothesis is that oracles with small Kolmogorov complexity are suitable. This hypothesis turns out to be true for an appropriately resource-bounded Kolmotorov complexity. Other complexity classes and relationships between them can also be reformulated and alyzed in terms of \(K_ b(x)\). One such reformulation is given in a paper by \textit{D. W. Juedes} and \textit{J. H. Lutz}. They prove that almost all EXPSPACE problem are not EXPSPACE-complete, and that complete EXPSPACE problems have unusually small space-bounded Kolmogorov complexity. Crudely speaking, this means that a randomly picked EXPSPACE problem is not as hard as the worst of them; however, if we consider problems with simple formulations, they are very hard to solve. \textit{L. Longpré} modifies the Martin-Löf definition of a random sequence (a sequence that survives an arbitrary algorithmic randomness test), and calls a sequence random if it survives an arbitrary resource- bounded algorithmic test. The resulting notion is related to \(K_ b(x)\) and to pseudo random number generators. The last paper, by \textit{V. A. Uspensky}, analyzes the cases when in the definition of Kolmogorov complexity, we allow the problem to generate something else in addition to \(x\) (e.g., generate \(x\) and go on computing something else; or, generate some preliminary comments and only then print \(x\)). These modifications are reasonable when we analyze a finite (observed) segment \(x\) of an infinite physical sequence; in this case, the fact that we took \(x\) and not some extension of \(x\) is rather irrelevant.

Recommendations

Cited in

(43)

This page was built for publication: Kolmogorov complexity and computational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4023359)