Quantitative Relativizations of Complexity Classes

DOI10.1137/0213030zbMath0599.03041OpenAlexW1992972561MaRDI QIDQ3734382

Ronald V. Book, Selman, Alan L., Timothy J. Long

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213030

zbMATH Keywords

complexity classesPSPACENPPco-NPbounding the size of the set of queriespolynomial time-bounded oracle machinesrestricted relativization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Related Items (45)

New lowness results for ZPP\(^{\text{NP}}\) and other complexity classes. ⋮ A taxonomy of complexity classes of functions ⋮ UNIFORM CHARACTERIZATIONS OF COMPLEXITY CLASSES OF FUNCTIONS ⋮ On bounded query machines ⋮ Nondeterministic functions and the existence of optimal proof systems ⋮ Separation with the Ruzzo, Simon, and Tompa relativization implies DSPACE(log n)\(\neq NSPACE(\log \,n)\) ⋮ Functions computable with limited access to NP ⋮ Positive relativizations for log space computability ⋮ Reductions between disjoint NP-pairs ⋮ Cluster computing and the power of edge recognition ⋮ On sparse oracles separating feasible complexity classes ⋮ Average-case intractability vs. worst-case intractability ⋮ Positive relativizations of the \(P=?\) NP problem ⋮ A refinement of the low and high hierarchies ⋮ Tractable counting of the answers to conjunctive queries ⋮ Promise problems and access to unambiguous computation ⋮ RelativizedNC ⋮ The Shrinking Property for NP and coNP ⋮ Pseudorandom generators against advised context-free languages ⋮ The shrinking property for NP and coNP ⋮ On relativizations with restricted number of accesses to the oracle set ⋮ The difference and truth-table hierarchies for NP ⋮ 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 ⋮ The consequences of eliminating NP solutions ⋮ Inverting onto functions. ⋮ ANALYSIS OF QUANTUM FUNCTIONS ⋮ Strong and robustly strong polynomial-time reducibilities to sparse sets ⋮ Solutions to twisted word equations and equations in virtually free groups ⋮ ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES ⋮ Optimal advice ⋮ Turing machines with few accepting computations and low sets for PP ⋮ The strong exponential hierarchy collapses ⋮ Coalgebraic Hybrid Logic ⋮ On hiding information from an oracle ⋮ A note on sparse sets and the polynomial-time hierarchy ⋮ A hierarchy based on output multiplicity ⋮ Sets with small generalized Kolmogorov complexity ⋮ Exact learning via teaching assistants ⋮ SELF-SPECIFYING MACHINES ⋮ Bounded queries, approximations, and the Boolean hierarchy ⋮ Qualitative relativizations of complexity classes ⋮ Robust algorithms: a different approach to oracles ⋮ On some natural complete operators ⋮ Reducing the number of solutions of NP functions

This page was built for publication: Quantitative Relativizations of Complexity Classes