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

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

Cited in

(only showing first 100 items - show all)

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
Qualitative relativizations of complexity classes
On some natural complete operators
Relativized circuit complexity
Independence results about context-free languages and lower bounds
Complete divisibility problems for slowly utilized oracles
Continuous optimization problems and a polynomial hierarchy of real functions
Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n) NSPACE( \,n)
A comparison of polynomial time completeness notions
The complexity of optimization problems
Diagonalizations over polynomial time computable sets
Random oracles separate PSPACE from the polynomial-time hierarchy
Relativized alternation and space-bounded computation
On sparse oracles separating feasible complexity classes
Probabilistic quantifiers and games
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?
Positive relativizations of the $P=?$ NP problem
Some more independence results in complexity theory
Discrete extremal problems
Bounded query machines: on NP and PSPACE
Bounded query machines: on NP( ) and NPQUERY( )
A note on sparse oracles for NP
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
Generic oracles, uniform machines, and codes
Separating complexity classes with tally oracles
Restricted relativizations of probabilistic polynomial time
Oracles for structural properties: The isomorphism problem and public-key cryptography
Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets
A uniform approach to define complexity classes
Diagonalization, uniformity, and fixed-point theorems
Circuit size relative to pseudorandom oracles
The generic oracle hypothesis is false
A comparison of polynomial time reducibilities
Relative complexity of checking and evaluating
The polynomial-time hierarchy
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
Some descriptive-set-theoretical problems in complexity theory
The random oracle hypothesis is false
Minimal pairs and complete problems
A note on the density of oracle decreasing time-space complexity
Relativizations of the P=?NP question over the reals (and other ordered rings)
A general method to construct oracles realizing given relationships between complexity classes
On P-immunity of exponential time complete sets
Separating classes in the exponential-time hierarchy from classes in PH
A tight relationship between generic oracles and type-2 complexity theory
$\mathcal P = \mathcal{NP}$?
Inverting onto functions.
Undecidability results for low complexity time classes
On the limits of gate elimination
Relativizing relativized computations
Degrees of Dowd-type generic oracles
Complexity of the $r$-query tautologies in the presence of a generic oracle
One-way permutations and self-witnessing languages
On the lattices of NP-subspaces of a polynomial time vector space over a finite field
A note on non-complete problems in $NP_\mathbb{R}$
What one has to know when attacking $\mathsf{P}$ vs.$\mathsf{NP}$
On low for speed oracles
How much randomness is needed to convert MA protocols to AM protocols?
Timed games with bounded window parity objectives
Lower bounds and hardness magnification for sublinear-time shrinking cellular automata
Does the polynomial hierarchy collapse if onto functions are invertible?
On computational complexity and honest polynomial degrees
On the metamathematics of the P vs. NP question
A novel characterization of the complexity class $\Theta_k^{\mathrm{P}}$ based on counting and comparison
Block-symmetric polynomials correlate with parity better than symmetric
Quantum certificate complexity
Quantum and classical complexity classes: Separations, collapses, and closure properties
On the complexity of constructing pseudorandom functions (especially when they don't exist)
Sets without subsets of higher many-one degree
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
$\mathrm P \overset {?} {=} \mathrm{NP}$
Axiomatizing physical experiments as oracles to algorithms
On the limit of some algorithmic approach to circuit lower bounds
Unprovability of circuit upper bounds in Cook's theory PV
Classes of bounded nondeterminism
A note on relativized log space
Quantum computing and hidden variables
Pseudoentropy: lower-bounds for chain rules and transformations
Nonuniform ACC circuit lower bounds
Self-reducible sets of small density

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)