Computing Solutions Uniquely Collapses the Polynomial Hierarchy
From MaRDI portal
Publication:4895826
DOI10.1137/S0097539794268315zbMath0857.68045OpenAlexW2092130624MaRDI QIDQ4895826
Ashish V. Naik, Ogihara, Mitsunori, Hemaspaandra, Lane A., Selman, Alan L.
Publication date: 16 October 1996
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539794268315
Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Related Items
Resource-bounded kolmogorov complexity revisited ⋮ Reductions between disjoint NP-pairs ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ Polynomial-time axioms of choice and polynomial-time cardinality ⋮ The Shrinking Property for NP and coNP ⋮ Testing the satisfiability of algebraic formulas over the field of two elements ⋮ The shrinking property for NP and coNP ⋮ The consequences of eliminating NP solutions ⋮ Inverting onto functions. ⋮ The Boolean hierarchy of NP-partitions ⋮ Pseudo-deterministic Proofs ⋮ ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES ⋮ Reducibility classes of P-selective sets ⋮ Some results on selectivity and self-reducibility ⋮ Optimal advice ⋮ P-selectivity: Intersections and indices ⋮ On the reducibility of sets inside NP to sets with low information content ⋮ Competing provers yield improved Karp-Lipton collapse results ⋮ Complexity classes of equivalence problems revisited ⋮ A hierarchy based on output multiplicity ⋮ Boolean operations, joins, and the extended low hierarchy ⋮ Resource bounded immunity and simplicity ⋮ Reducing the number of solutions of NP functions
