Kolmogorov complexity and computational complexity (Q4023359)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 107775
Language Label Description Also known as
default for all languages
No label defined
    English
    Kolmogorov complexity and computational complexity
    scientific article; zbMATH DE number 107775

      Statements

      23 January 1993
      0 references
      Kolmogorov complexity
      0 references
      Computational complexity
      0 references
      computational complexity theory
      0 references
      resource-bounded programs
      0 references
      oracle complexity
      0 references
      Kolmogorov complexity and computational complexity (English)
      0 references
      [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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references