Computing Solutions Uniquely Collapses the Polynomial Hierarchy

DOI10.1137/S0097539794268315MaRDI QIDQ4895826zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, Ashish V. Naik, Ogihara, Mitsunori, Alan L. Selman

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

zbMATH Keywords

computational complexitynonuniform complexitysemidecision algorithms

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the complexity of unique solutions
• On collapsing the polynomial-time hierarchy
• scientific article; zbMATH DE number 3928209
• Publication:4944898
• Collapsing exact arithmetic hierarchies
• Computing all solutions to polynomial systems using homotopy continuation
• A Downward Collapse within the Polynomial Hierarchy
• Computing the multiplicity structure in solving polynomial systems
• scientific article; zbMATH DE number 7120932
• Computing singular solutions to polynomial systems

Cited in

(27)

• A hierarchy based on output multiplicity
• Boolean operations, joins, and the extended low hierarchy
• Inverting onto functions.
• Reducing the number of solutions of NP functions
• On the reducibility of sets inside NP to sets with low information content
• Competing provers yield improved Karp-Lipton collapse results
• Reductions between disjoint NP-pairs
• Resource bounded immunity and simplicity
• The Shrinking Property for NP and coNP
• Is Valiant-Vazirani's isolation probability improvable?
• A Downward Collapse within the Polynomial Hierarchy
• scientific article; zbMATH DE number 1759426 (Why is no real title available?)
• The consequences of eliminating NP solutions
• Pseudo-deterministic proofs
• Resource-bounded Kolmogorov complexity revisited
• ADVICE FOR SEMIFEASIBLE SETS AND THE COMPLEXITY-THEORETIC COST(LESSNESS) OF ALGEBRAIC PROPERTIES
• Polynomial-time axioms of choice and polynomial-time cardinality
• Testing the satisfiability of algebraic formulas over the field of two elements
• The shrinking property for NP and coNP
• Reducibility classes of P-selective sets
• Some results on selectivity and self-reducibility
• Optimal advice
• P-selectivity: Intersections and indices
• Complexity classes of equivalence problems revisited
• Symmetric exponential time requires near-maximum circuit size
• The complexity of computing second solutions
• The Boolean hierarchy of NP-partitions

This page was built for publication: Computing Solutions Uniquely Collapses the Polynomial Hierarchy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4895826)