Some hierarchies of relativized time-bounded complexity classes (Q1070822)

Summary: Some results on relativized time-bounded complexity classes are presented. There can be many kinds of hierarchies of complexity subclasses of relativized NP. For brevity, let P(A,k) [NP(A,k)] be the relativized complexity class \(DTIME^ A(n^ k)\) [resp. \(NTIME^ A(n^ k)]\) with respect to oracle set A. (For \(k=1\), replace \(n^ k\) by 2n). Then for example: 1) There is an oracle set A such that for all \(k>0\) P(A,k) is properly contained in NP(A,k) and NP(A,k) is properly contained in \(P(A,k+1)\). 2) For each \(k>0\), there is an oracle set D (depending on k) such that for any \(i\leq k\) P(D,i)\(\neq NP(D,i)\) but for all \(j>k\) \(P(D,j)=NP(D,j)\). Besides, we show a theorem which is a higher level analog to a theorem of \textit{R. V. Book}, \textit{C. B. Wilson} and \textit{Xu Mei-Rui} [SIAM J. Comput. 11, 571-581 (1982; Zbl 0487.68038)].