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

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 coNP^ A from P^ A by random oracles A?
Robust machines accept easy sets
On low for speed oracles
Space bounded computations: Review and new separation results
Block-symmetric polynomials correlate with parity better than symmetric
$\mathrm P \overset {?} {=} \mathrm{NP}$
Immunity, simplicity, probabilistic complexity classes and relativizations
Are there interactive protocols for co-NP languages?
Probabilistic quantifiers and games
Separating complexity classes with tally oracles
$\mathcal P = \mathcal{NP}$?
Inseparability and strong hypotheses for disjoint NP pairs
Timed games with bounded window parity objectives
On languages specified by relative acceptance
A beautiful theorem
Constructive separations and their consequences
The random oracle hypothesis is false
The complexity of Grigorchuk groups with application to cryptography
Independence results about context-free languages and lower bounds
Degrees of Dowd-type generic oracles
Non-Black-Box Worst-Case to Average-Case Reductions Within $\mathsf{NP}$
Complexity of the $r$-query tautologies in the presence of a generic oracle
Minimal pairs and complete problems
On the power of statistical zero knowledge
Quantum vs. classical proofs and subset verification
On relativizations of the P =? NP question for several structures
A comparison of polynomial time completeness notions
P versus NP and computability theoretic constructions in complexity theory over algebraic structures
Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
One-way permutations and self-witnessing languages
A hierarchy that does not collapse : alternations in low level space
Oracle Quantum Computing
Quantum computing and hidden variables
The complexity of optimization problems
On low for speed oracles
Qualitative relativizations of complexity classes
Log space machines with multiple oracle tapes
Complexity classes of equivalence problems revisited
Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics
A measure of relativized space which is faithful with respect to depth
Calculs sur les structures de langage dénombrable
A uniform approach to define complexity classes
A note on separating the relativized polynomial time hierarchy by immune sets
Structural properties of oracle classes
Self-reducible sets of small density
A second step toward the strong polynomial-time hierarchy
Classes of bounded nondeterminism
Relativized alternation and space-bounded computation
On the polynomial IO-complexity
On the limits of gate elimination
Complexity barriers as independence
Relativized polynomial hierarchies extending two levels
New developments in structural complexity theory
On computational complexity and honest polynomial degrees
A hierarchy theorem for interactive proofs of proximity
Complete sets and the polynomial-time hierarchy
Arithmetical hierarchy and complexity of computation
Immunity and simplicity in relativizations of probabilistic complexity classes
On relativizing auxiliary pushdown machines
Relativized generic classes P and NP
Positive relativizations for log space computability
Pseudoentropy: lower-bounds for chain rules and transformations
UP and the low and high hierarchies: A relativized separation
Black-Box and Data-Driven Computation
Statistical randomized encodings: a complexity theoretic view
Relativized counting classes: Relations among thresholds, parity, and mods
Some more independence results in complexity theory
Discrete extremal problems
Quantum certificate complexity
On sparse oracles separating feasible complexity classes
Bounded query machines: on NP and PSPACE
Does the polynomial hierarchy collapse if onto functions are invertible?
Relativized circuit complexity
Unprovability of circuit upper bounds in Cook's theory PV
With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy
Forcing in Proof Theory
The polynomial-time hierarchy
Informal versus formal mathematics
On some natural complete operators
A tight relationship between generic oracles and type-2 complexity theory
The strong exponential hierarchy collapses
Natural proofs
A note on non-complete problems in $NP_\mathbb{R}$
Relativization and interactive proof systems in parameterized complexity theory
Circuit size relative to pseudorandom oracles
On counting problems and the polynomial-time hierarchy
A note on relativized log space
Quantum and classical complexity classes: Separations, collapses, and closure properties
A general method to construct oracles realizing given relationships between complexity classes
On the lattices of NP-subspaces of a polynomial time vector space over a finite field
On Horn spectra
Nonuniform ACC circuit lower bounds
Some descriptive-set-theoretical problems in complexity theory
A time-luck tradeoff in relativized cryptography
An appraisal of computational complexity for operations researchers
Undecidability results for low complexity time classes
Separating the low and high hierarchies by oracles

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)