On collapsing the polynomial-time hierarchy

DOI10.1016/0020-0190(94)00157-XzbMath0938.68663WikidataQ61687092 ScholiaQ61687092MaRDI QIDQ1339382

Ronald V. Book

Publication date: 21 June 2000

Published in: Information Processing Letters (Search for Journal in Brave)

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Hausdorff dimension and oracle constructions ⋮ Relative to a random oracle, P/poly is not measurable in EXP ⋮ Relativized worlds with an infinite hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Probabilistic complexity classes and lowness
• Process complexity and effective random tests
• Some Observations on Separating Complexity Classes
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• A Theory of Program Size Formally Identical to Information Theory
• An observation on probability versus randomness with applications to complexity classes
• On Languages Reducible to Algorithmically Random Languages
• The definition of random sequences

This page was built for publication: On collapsing the polynomial-time hierarchy