JavaScript is disabled for your browser. Some features of this site may not work without it.
Can P and NP Manufacture Randomness?

Author
Hemachandra, Lane A.
Abstract
This paper studies how Kolmogorov complexity dictates the structure of standard deterministic and nondeterministic classes. We completely characterize, in Kolmogorov terms, when $P^{NP[\log]}= P^{NP}$, where [log] indicates that $O(\log n)$ oracle calls are made. We give a Kolmogorov characterization of P=NP that links the work of Adleman and Krentel. Briefly stated, complexity classes collapse unless they can manufacture randomness. A $\Delta^{p}_{2}$ machine is a P machine with an NP oracle. The series of replies the NP oracle makes is called the pronouncement. We show that $P^{NP[\log]}= P^{NP}$ if and only if each $\Delta^{p}_{2}$ language is accepted by some $\Delta^{p}_{2}$ machine with Kolmogorov simple pronouncements. (i.e., $(\forall P_{i}) (\exists c) (\forall x) [Pronouncements_{P_{i}}$ SAT $(x) \in K[c \log n, n^{c} | x]])$. Turning to functions, we show that: $P^{NP[\log]}F = P^{NP}F$ if and only if all $\Delta^{p}_{2}$ machines have Kolmogorov simple pronouncements. Since $P^{NP[\log]}F = P^{NP}F \Longleftrightarrow$ P=NP (Krentel), the above gives an alternate Kolmogorov characterization of the P=NP question, which complements Adleman's classic characterization. Our key technique is an oracle-based divide and conquer over a tree of potential pronouncements. The results generalize to many other classes, including truth-table classes and counting classes. Thus, Kolmogorov complexity dictates the structure of the classes that are at the center of our understanding of feasible computation.
Date Issued
1986-12Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-795
Type
technical report