On relativized nondeterministic polynomial-time bounded computations

DOI10.1080/00207168508803457zbMath0558.68041OpenAlexW59272652MaRDI QIDQ3347297

Li Xiang

Publication date: 1985

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168508803457

zbMATH Keywords

nondeterminismpolynomial-time hierarchyrelativized classesnondeterministic Turing machinesrecursive oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Immunity, simplicity, probabilistic complexity classes and relativizations

Cites Work

• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Recursively enumerable sets and degrees