Relativized polynomial hierarchies extending two levels

DOI10.1007/BF01744434zbMath0543.03028MaRDI QIDQ3331211

Hans Heller

Publication date: 1984

Published in: Mathematical Systems Theory (Search for Journal in Brave)

zbMATH Keywords

oracle machinesP\(=NP\) problempolynomially bounded quantifiersRelativized polynomial hierarchies

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Hierarchies of computability and definability (03D55)

Related Items (9)

Census techniques collapse space classes ⋮ On \(\Delta ^ P_ 2\)-immunity ⋮ Relativized alternation and space-bounded computation ⋮ The difference and truth-table hierarchies for NP ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ Easiness assumptions and hardness tests: Trading time for zero error ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ Undecidability results for low complexity time classes ⋮ On some natural complete operators

Cites Work

• Complete sets and the polynomial-time hierarchy
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Relativized polynomial hierarchies extending two levels