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

DOI10.1137/0204037zbMATH Open0323.68033DBLPjournals/siamcomp/BakerGS75OpenAlexW1993138363WikidataQ55871787 ScholiaQ55871787MaRDI QIDQ4086709FDOQ4086709

Authors: 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

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

Cited In (only showing first 100 items - show all)

• A comparison of polynomial time reducibilities
• Relative complexity of checking and evaluating
• Positive relativizations of the \(P=?\) NP problem
• Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?
• Robust machines accept easy sets
• Space bounded computations: Review and new separation results
• Are there interactive protocols for co-NP languages?
• Probabilistic quantifiers and games
• Separating complexity classes with tally oracles
• Inseparability and strong hypotheses for disjoint NP pairs
• The random oracle hypothesis is false
• Independence results about context-free languages and lower bounds
• The complexity of Grigorchuk groups with application to cryptography
• Fault-tolerance and complexity (Extended abstract)
• A hierarchy that does not collapse : alternations in low level space
• A comparison of polynomial time completeness notions
• Oracle Quantum Computing
• One-way permutations and self-witnessing languages
• Quantum computing and hidden variables
• Barriers for Rank Methods in Arithmetic Complexity
• The complexity of optimization problems
• On the Limit of Some Algorithmic Approach to Circuit Lower Bounds
• Qualitative relativizations of complexity classes
• Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
• Complexity classes of equivalence problems revisited
• A measure of relativized space which is faithful with respect to depth
• A uniform approach to define complexity classes
• Classes of bounded nondeterminism
• Relativized alternation and space-bounded computation
• On the polynomial IO-complexity
• On computational complexity and honest polynomial degrees
• New developments in structural complexity theory
• Complete sets and the polynomial-time hierarchy
• Arithmetical hierarchy and complexity of computation
• Relativized counting classes: Relations among thresholds, parity, and mods
• Quantum certificate complexity
• On sparse oracles separating feasible complexity classes
• Does the polynomial hierarchy collapse if onto functions are invertible?
• Forcing in Proof Theory
• Bounded query machines: on NP and PSPACE
• Relativized circuit complexity
• With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
• Natural proofs
• The polynomial-time hierarchy
• On some natural complete operators
• A tight relationship between generic oracles and type-2 complexity theory
• The strong exponential hierarchy collapses
• A note on non-complete problems in \(NP_\mathbb{R}\)
• Circuit size relative to pseudorandom oracles
• On counting problems and the polynomial-time hierarchy
• A general method to construct oracles realizing given relationships between complexity classes
• On Horn spectra
• Some descriptive-set-theoretical problems in complexity theory
• Undecidability results for low complexity time classes
• Axiomatizing physical experiments as oracles to algorithms
• A Universal Approach to Self-Referential Paradoxes, Incompleteness and Fixed Points
• Strong nondeterministic polynomial-time reducibilities
• On the metamathematics of the P vs. NP question
• Lower bounds on the worst-case complexity of some oracle algorithms
• Relativizing relativized computations
• Sets without subsets of higher many-one degree
• Bounded arithmetic and the polynomial hierarchy
• Separating classes in the exponential-time hierarchy from classes in PH
• Structural complexity theory: Recent surprises
• Oracles for structural properties: The isomorphism problem and public-key cryptography
• On the Power of Statistical Zero Knowledge
• Limits on alternation trading proofs for time-space lower bounds
• The polynomial hierarchy and a simple model for competitive analysis
• Classifying the computational complexity of problems
• Statistical Randomized Encodings: A Complexity Theoretic View
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Inverting onto functions.
• A low and a high hierarchy within NP
• A refinement of the low and high hierarchies
• RelativizedNC
• One-way functions and the nonisomorphism of NP-complete sets
• Reducibilities on real numbers
• Oracle-dependent properties of the lattice of NP sets
• Nonuniform ACC Circuit Lower Bounds
• Relativization of questions about log space computability
• Diagonalizations over polynomial time computable sets
• Theory of one-tape linear-time Turing machines
• Immunity and Simplicity for Exact Counting and Other Counting Classes
• Parity, circuits, and the polynomial-time hierarchy
• Simultaneous strong separations of probabilistic and unambiguous complexity classes
• A note on sparse oracles for NP
• On the acceptance power of regular languages
• The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
• Relativized isomorphisms of NP-complete sets
• Block-symmetric polynomials correlate with parity better than symmetric
• Immunity, simplicity, probabilistic complexity classes and relativizations
• Constructive separations and their consequences
• \(\mathcal P = \mathcal{NP}\)?
• Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
• Timed games with bounded window parity objectives
• Title not available (Why is that?)
• On languages specified by relative acceptance
• Degrees of Dowd-type generic oracles
• Complexity of the \(r\)-query tautologies in the presence of a generic oracle
• On relativizations of the P =? NP question for several structures

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

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