Some hierarchies of relativized time-bounded complexity classes
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)].
- Almost-everywhere complexity hierarchies for nondeterministic time
- Determining the levels of some special complexity classes of sets in the Kleene arithmetical hierarchy
- Relating the bounded arithmetic and polynomial time hierarchies
- On relativized nondeterministic polynomial-time bounded computations
- scientific article; zbMATH DE number 3958736 (Why is no real title available?)
- On Tally Relativizations of $BP$-Complexity Classes
- A time-space hierarchy between polynomial time and polynomial space
This page was built for publication: Some hierarchies of relativized time-bounded complexity classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1070822)
