Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
From MaRDI portal
Publication:4086709
DOI10.1137/0204037zbMath0323.68033OpenAlexW1993138363WikidataQ55871787 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
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
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, On the lattices of NP-subspaces of a polynomial time vector space over a finite field, Block-symmetric polynomials correlate with parity better than symmetric, Informal versus formal mathematics, Some more independence results in complexity theory, \(\mathcal P = \mathcal{NP}\)?, Discrete extremal problems, Bounded query machines: on NP and PSPACE, Bounded query machines: on NP( ) and NPQUERY( ), Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A?, New developments in structural complexity theory, Robust machines accept easy sets, Complexity-theoretic algebra. II: Boolean algebras, A note on sparse oracles for NP, Inverting onto functions., A time-luck tradeoff in relativized cryptography, On counting problems and the polynomial-time hierarchy, An appraisal of computational complexity for operations researchers, Space bounded computations: Review and new separation results, Bounded arithmetic and the polynomial hierarchy, The complexity of Grigorchuk groups with application to cryptography, Optimal algorithms for co-NP-sets and the EXP\(\overset{!}{ = }\)NEXP problem, An NL hierarchy, A note on non-complete problems in \(NP_\mathbb{R}\), Generic oracles, uniform machines, and codes, Separating complexity classes with tally oracles, Restricted relativizations of probabilistic polynomial time, Limits on alternation trading proofs for time-space lower bounds, On the acceptance power of regular languages, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, Oracles for structural properties: The isomorphism problem and public-key cryptography, Quantum certificate complexity, Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets, Relativized isomorphisms of NP-complete sets, A uniform approach to define complexity classes, Diagonalization, uniformity, and fixed-point theorems, Inseparability and strong hypotheses for disjoint NP pairs, Circuit size relative to pseudorandom oracles, The generic oracle hypothesis is false, Quantum and classical complexity classes: Separations, collapses, and closure properties, What one has to know when attacking \(\mathsf{P}\) vs.\(\mathsf{NP}\), On low for speed oracles, Does the polynomial hierarchy collapse if onto functions are invertible?, A comparison of polynomial time reducibilities, Complexity classes of equivalence problems revisited, Relative complexity of checking and evaluating, On computational complexity and honest polynomial degrees, The polynomial-time hierarchy, On the polynomial IO-complexity, The strong exponential hierarchy collapses, Structural properties of oracle classes, Complete sets and the polynomial-time hierarchy, Log space machines with multiple oracle tapes, On languages specified by relative acceptance, Lower bounds on the worst-case complexity of some oracle algorithms, Arithmetical hierarchy and complexity of computation, On Horn spectra, Relativizing relativized computations, Undecidability results for low complexity time classes, Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics, Theory of one-tape linear-time Turing machines, A low and a high hierarchy within NP, Strong nondeterministic polynomial-time reducibilities, Reducibilities on real numbers, Oracle-dependent properties of the lattice of NP sets, How much randomness is needed to convert MA protocols to AM protocols?, Degrees of Dowd-type generic oracles, Qualitative relativizations of complexity classes, On some natural complete operators, Complexity of the \(r\)-query tautologies in the presence of a generic oracle, Relativized circuit complexity, Timed games with bounded window parity objectives, Independence results about context-free languages and lower bounds, Lower bounds and hardness magnification for sublinear-time shrinking cellular automata, 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
