On relativized nondeterministic polynomial-time bounded computations
Li. Xiang · International Journal of Computer Mathematics · 1985
We prove that for any k≧l there exists a recursive oracle A⊆{0,1}∗ such that some set in has no infinite subset in where is accepted by a X nondeterministic polynomial time bounded Turing machine with oracle A⊆{0,1}∗ making at most ni nondeterministic moves on any input of length n}.