Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
From MaRDI portal
Publication:3902480
DOI10.1137/0210008zbMath0454.68030OpenAlexW2062767125WikidataQ55887618 ScholiaQ55887618MaRDI QIDQ3902480
Publication date: 1981
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0210008
polynomial reducibilityprobabilistic computationnondeterministic computationrelativized computationpolynomial isomorphismpolynomial immunity
Related Items
On randomized versus deterministic computation ⋮ Structural complexity theory: Recent surprises ⋮ On closure properties of bounded two-sided error complexity classes ⋮ On the power of parity polynomial time ⋮ On complexity classes and algorithmically random languages ⋮ Sets computable in polynomial time on average ⋮ Borel complexity and Ramsey largeness of sets of oracles separating complexity classes ⋮ On the computational power of probabilistic and faulty neural networks ⋮ On the cutting edge of relativization: The resource bounded injury method ⋮ Strong self-reducibility precludes strong immunity ⋮ On the power of parity polynomial time ⋮ Approximate counting in bounded arithmetic ⋮ On the robustness of ALMOST-$\mathcal {R}$ ⋮ Almost every set in exponential time is P-bi-immune ⋮ Genericity and measure for exponential time ⋮ Complete sets and closeness to complexity classes ⋮ Generix strikes again ⋮ The expressive power of voting polynomials ⋮ One-way permutations and self-witnessing languages ⋮ The random oracle hypothesis is false ⋮ Complete divisibility problems for slowly utilized oracles ⋮ Computational depth: Concept and applications ⋮ Hausdorff dimension and oracle constructions ⋮ On collapsing the polynomial-time hierarchy ⋮ Approximation to measurable functions and its relation to probabilistic computation ⋮ Nonlevelable sets and immune sets in the accepting density hierarchy inNP ⋮ Immunity and Simplicity for Exact Counting and Other Counting Classes ⋮ New Limits to Classical and Quantum Instance Compression ⋮ On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes ⋮ Computation times of NP sets of different densities ⋮ A comparison of polynomial time completeness notions ⋮ Genericity and measure for exponential time ⋮ A classification of complexity core lattices ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Polynomial-time reducibilities and ``almost all oracle sets ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ Bounded truth table does not reduce the one-query tautologies to a random oracle ⋮ Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes ⋮ Diagonalizations over polynomial time computable sets ⋮ Does co-NP have short interactive proofs ? ⋮ Random oracles separate PSPACE from the polynomial-time hierarchy ⋮ Complexity classes without machines: on complete languages for UP ⋮ On randomized versus deterministic computation ⋮ Probabilistic quantifiers and games ⋮ Simplicity, immunity, relativizations and nondeterminism ⋮ Graph isomorphism is in the low hierarchy ⋮ With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy ⋮ An observation on probability versus randomness with applications to complexity classes ⋮ A note on separating the relativized polynomial time hierarchy by immune sets ⋮ Weakly complete problems are not rare ⋮ On the lattices of NP-subspaces of a polynomial time vector space over a finite field ⋮ An improved zero-one law for algorithmically random sequences ⋮ Characterizing polynomial complexity classes by reducibilities ⋮ A lower bound for randomized algebraic decision trees ⋮ Structural analysis of the complexity of inverse functions ⋮ Time evolution of complexity: a critique of three methods ⋮ An oracle builder's toolkit ⋮ The Shrinking Property for NP and coNP ⋮ P-immune sets with holes lack self-reducibility properties. ⋮ The shrinking property for NP and coNP ⋮ Forcing complexity: Minimum sizes of forcing conditions. ⋮ Classifying the computational complexity of problems ⋮ Query complexity, or why is it difficult to separate \(NP^ A\cap coNP^ A\) from \(P^ A\) by random oracles A? ⋮ OnP-subset structures ⋮ Complexity-theoretic algebra. II: Boolean algebras ⋮ Some observations on the probabilistic algorithms and NP-hard problems ⋮ Lower bounds for constant-depth circuits in the presence of help bits ⋮ Bi-immunity results for cheatable sets ⋮ Complexity limitations on quantum computation ⋮ Hard sets are hard to find ⋮ Inverting onto functions. ⋮ On random oracle separations ⋮ Generic oracles, uniform machines, and codes ⋮ On independent random oracles ⋮ Immunity, simplicity, probabilistic complexity classes and relativizations ⋮ A second step toward the strong polynomial-time hierarchy ⋮ The relativized relationship between probabilistically checkable debate systems, IP and PSPACE ⋮ Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas ⋮ Does truth-table of linear norm reduce the one-query tautologies to a random oracle? ⋮ Circuit depth relative to a random oracle ⋮ Probabilistic polynomials, AC\(^ 0\) functions and the polynomial-time hierarchy ⋮ Polynomial-time compression ⋮ Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets ⋮ Improving known solutions is hard ⋮ Relativized isomorphisms of NP-complete sets ⋮ A uniform approach to define complexity classes ⋮ Diagonalization, uniformity, and fixed-point theorems ⋮ Using the renormalization group to classify Boolean functions ⋮ Circuit size relative to pseudorandom oracles ⋮ On read-once vs. multiple access to randomness in logspace ⋮ The generic oracle hypothesis is false ⋮ Structural properties of oracle classes ⋮ Dimension extractors and optimal decompression ⋮ Probabilistic complexity classes and lowness ⋮ An oracle separating \(\oplus P\) from \(PP^{PH}\) ⋮ $$P\mathop{ =}\limits^{?}NP$$ ⋮ A hierarchy based on output multiplicity ⋮ Simulating probabilistic by deterministic algebraic computation trees ⋮ Some consequences of the existnce of pseudorandom generators ⋮ Multifunction algebras and the provability of \(PH\downarrow\) ⋮ Randomised algorithms ⋮ BPP and the polynomial hierarchy ⋮ On self-reducibility and weak P-selectivity ⋮ Oracle-dependent properties of the lattice of NP sets ⋮ Resource bounded immunity and simplicity ⋮ Almost-everywhere superiority for quantum polynomial time ⋮ Degrees of Dowd-type generic oracles ⋮ ``NP\(=\)P? and restricted partitions ⋮ Space-bounded hierarchies and probabilistic computations ⋮ On some natural complete operators ⋮ Complexity of the \(r\)-query tautologies in the presence of a generic oracle ⋮ An upward measure separation theorem ⋮ Relativized circuit complexity ⋮ Bi-immune sets for complexity classes ⋮ Relativized worlds with an infinite hierarchy ⋮ \(BPP\) has subexponential time simulations unless \(EXPTIME\) has publishable proofs ⋮ Randomness in interactive proofs
