Refining Nondeterminism in Relativized Polynomial-Time Bounded Computations
Chandra M. R. Kintala, Patrick C. Fischer · SIAM Journal on Computing · 1980
Let $\mathcal {P}_{g(n)} $ denote the class of languages acceptable by polynomial-time bounded Turing machines making at most $g(n)$ nondeterministic moves on inputs of length n. For any constructible $g(n)$,$\mathcal {P} \subseteq \mathcal {P}_{g(n)} \subseteq \mathcal {N}\mathcal {P}$The classes $\mathcal {P}_{g(n)} $, for various $g(n)$ of the form $(\log n)^k ,k \geqq 1$, are relativized and the relationships among those relativized classes are studied. In particular, oracle sets are constructed which (1) make all the relativized classes equal (this follows from Baker, Gill and Solovay (1975)); (2) make all the classes associated with powers of $\log n$ different; (3) for any k, make all the classes below $(\log n)^k $ different while the kth power class is equal to relativized $\mathcal {NP}$. Results regarding closure of the $(\log n)^k $ classes under complementation are also given.