Counting random oracles for the polynomial-time hierarchy and quantum complexity classes

DOI10.1007/978-3-032-31348-5_22MaRDI QIDQ7411975zbMATH OpenFDO

Authors John M. Hitchcock, Adewale Sekoni, Hadi Shafei

Publication date 2027

Full work available at URL https://doi.org/10.1007/978-3-032-31348-5_22

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• Almost every set in exponential time is P-bi-immune
• Almost everywhere high nonuniform complexity
• An average-case depth hierarchy theorem for Boolean circuits
• An average-case depth hierarchy theorem for Boolean circuits
• An observation on probability versus randomness with applications to complexity classes
• Category and Measure in Complexity Classes
• Counting Classes are at Least as Hard as the Polynomial-Time Hierarchy
• Counting martingales for measure and dimension in complexity classes
• Determining acceptance possibility for a quantum computation is hard for the polynomial hierarchy
• Dimension in Complexity Classes
• Dimension, entropy rates, and compression
• Gap-definable counting classes
• Hausdorff dimension and oracle constructions
• How hard is it to approximate the Jones polynomial?
• scientific article; zbMATH DE number 1346358 (Why is no real title available?)
• scientific article; zbMATH DE number 1008517 (Why is no real title available?)
• scientific article; zbMATH DE number 1048036 (Why is no real title available?)
• scientific article; zbMATH DE number 3799016 (Why is no real title available?)
• scientific article; zbMATH DE number 1860654 (Why is no real title available?)
• On Approximation Algorithms for # P
• On counting and approximation
• On the random oracle hypothesis
• Polynomial-time random oracles and separating complexity classes
• Random oracles separate PSPACE from the polynomial-time hierarchy
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• Strengths and Weaknesses of Quantum Computing
• The acrobatics of BQP
• The complexity of combinatorial problems with succinct input representation
• The complexity of computing the permanent
• The definition of random sequences
• The quantitative structure of exponential time
• The random oracle hypothesis is false
• The zero-one law holds for BPP
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy

This page was built for publication: Counting random oracles for the polynomial-time hierarchy and quantum complexity classes

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