Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question

DOI10.1137/0204037zbMath0323.68033DBLPjournals/siamcomp/BakerGS75OpenAlexW1993138363WikidataQ55871787 ScholiaQ55871787MaRDI QIDQ4086709

John Gill, Robert M. Solovay, Theodore P. Baker

Publication date: 1975

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0204037

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (only showing first 100 items - show all)

Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ Statistical Randomized Encodings: A Complexity Theoretic View ⋮ A MINIMAL SET LOW FOR SPEED ⋮ The polynomial hierarchy and a simple model for competitive analysis ⋮ A Hierarchy Theorem for Interactive Proofs of Proximity ⋮ Structural complexity theory: Recent surprises ⋮ Pseudoentropy: Lower-Bounds for Chain Rules and Transformations ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Separating the low and high hierarchies by oracles ⋮ One-way functions and the nonisomorphism of NP-complete sets ⋮ Positive relativizations for log space computability ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ P versus NP and computability theoretic constructions in complexity theory over algebraic structures ⋮ Propositional proof systems, the consistency of first order theories and the complexity of computations ⋮ Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ Self-reducible sets of small density ⋮ Axiomatizing physical experiments as oracles to algorithms ⋮ A refinement of the low and high hierarchies ⋮ On Low for Speed Oracles ⋮ On the Limit of Some Algorithmic Approach to Circuit Lower Bounds ⋮ RelativizedNC ⋮ Logics capturing relativized complexity classes uniformly ⋮ Borel complexity and Ramsey largeness of sets of oracles separating complexity classes ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Communication and information complexity ⋮ On relativizations with restricted number of accesses to the oracle set ⋮ Classifying the computational complexity of problems ⋮ On the Power of Statistical Zero Knowledge ⋮ Immunity and simplicity in relativizations of probabilistic complexity classes ⋮ A Homological Theory of Functions: Nonuniform Boolean Complexity Separation and VC Dimension Bound Via Algebraic Topology, and a Homological Farkas Lemma ⋮ Barriers for Rank Methods in Arithmetic Complexity ⋮ Fault-tolerance and complexity (Extended abstract) ⋮ UP and the low and high hierarchies: A relativized separation ⋮ Strong self-reducibility precludes strong immunity ⋮ A hierarchy that does not collapse : alternations in low level space ⋮ Quantum vs Classical Proofs and Subset Verification ⋮ Immunity, simplicity, probabilistic complexity classes and relativizations ⋮ A second step toward the strong polynomial-time hierarchy ⋮ RELATIVIZED GENERIC CLASSES P AND NP ⋮ Black-Box and Data-Driven Computation ⋮ A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points ⋮ Relativization of questions about log space computability ⋮ Parity, circuits, and the polynomial-time hierarchy ⋮ On Relativizations of the P =? NP Question for Several Structures ⋮ Relativized polynomial hierarchies extending two levels ⋮ Classes of bounded nondeterminism ⋮ A note on relativized log space ⋮ On Complete Problems, Relativizations and Logics for Complexity Classes ⋮ Natural proofs ⋮ On relativized nondeterministic polynomial-time bounded computations ⋮ Forcing in Proof Theory ⋮ On relativizing auxiliary pushdown machines ⋮ Limits of Constructive Security Proofs ⋮ Unnamed Item ⋮ Reducibilities on tally and sparse sets ⋮ Calculs sur les structures de langage dénombrable ⋮ Unnamed Item ⋮ On the complexity of constructing pseudorandom functions (especially when they don't exist) ⋮ Unnamed Item ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ A Beautiful Theorem ⋮ Efficiency Bounds for Adversary Constructions in Black-Box Reductions ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Quantum computing and hidden variables ⋮ Unnamed Item ⋮ Generix strikes again ⋮ Sets without subsets of higher many-one degree ⋮ Oracle Quantum Computing ⋮ Unprovability of circuit upper bounds in Cook's theory PV ⋮ Some descriptive-set-theoretical problems in complexity theory ⋮ One-way permutations and self-witnessing languages ⋮ The random oracle hypothesis is false ⋮ Complete divisibility problems for slowly utilized oracles ⋮ Minimal pairs and complete problems ⋮ A note on the density of oracle decreasing time-space complexity ⋮ Continuous optimization problems and a polynomial hierarchy of real functions ⋮ Relativizations of the P=?NP question over the reals (and other ordered rings) ⋮ On the limits of gate elimination ⋮ Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) ⋮ A comparison of polynomial time completeness notions ⋮ A general method to construct oracles realizing given relationships between complexity classes ⋮ On the metamathematics of the P vs. NP question ⋮ The complexity of optimization problems ⋮ Diagonalizations over polynomial time computable sets ⋮ On P-immunity of exponential time complete sets ⋮ Random oracles separate PSPACE from the polynomial-time hierarchy ⋮ Separating classes in the exponential-time hierarchy from classes in PH ⋮ Relativized alternation and space-bounded computation ⋮ On sparse oracles separating feasible complexity classes ⋮ Probabilistic quantifiers and games ⋮ A tight relationship between generic oracles and type-2 complexity theory ⋮ A measure of relativized space which is faithful with respect to depth ⋮ With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy ⋮ Are there interactive protocols for co-NP languages? ⋮ A novel characterization of the complexity class \(\Theta_k^{\mathrm{P}}\) based on counting and comparison ⋮ Positive relativizations of the \(P=?\) NP problem

This page was built for publication: Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question