Can P and NP Manufacture Randomness?

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.