Relativized polynomial hierarchies extending two levels

DOI10.1007/BF01744434MaRDI QIDQ3331211zbMATH OpenFDO

Authors Hans Heller

Publication date 1984

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

Full work available at URL https://doi.org/10.1007/BF01744434

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 3871339
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• On Relativized Polynomial and Exponential Computations
• scientific article; zbMATH DE number 3930983
• Separating the low and high hierarchies by oracles

Cites work

• Complete sets and the polynomial-time hierarchy
• scientific article; zbMATH DE number 3815616 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3592966 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

Cited in

(15)

• On some natural complete operators
• On \(\Delta ^ P_ 2\)-immunity
• Relativized alternation and space-bounded computation
• Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
• Census techniques collapse space classes
• Undecidability results for low complexity time classes
• The polynomial hierarchy of functions and its levels
• scientific article; zbMATH DE number 3871339 (Why is no real title available?)
• The polynomial hierarchy for some structures over the binary words
• scientific article; zbMATH DE number 3930983 (Why is no real title available?)
• The difference and truth-table hierarchies for NP
• Relativized Polynomial Time Hierarchies Having Exactly K Levels
• A relationship between difference hierarchies and relativized polynomial hierarchies
• THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS
• Easiness assumptions and hardness tests: Trading time for zero error

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3331211)