Kolmogorov characterizations of complexity classes
Lane A. Hemaspaandra, Gerd Wechsung · Theoretical Computer Science · 1991
This paper completely characterizes the Θkp levels of the polynomial hierarchy in terms of Kolmogorov complexity. From the characterization, it follows that the Θkp and Δkp levels of the polynomial hierarchy are equal if and only if every Δkp language is accepted by some Δkp machine whose pronouncements (query answers) are Kolmogorov simple. Analogous results are obtained for the exponential hierarchy.