Reducing the number of solutions of NP functions
From MaRDI portal
Publication:1608321
DOI10.1006/jcss.2001.1815zbMath1018.68032MaRDI QIDQ1608321
Hemaspaandra, Lane A., Ogihara, Mitsunori, Gerd Wechsung
Publication date: 4 August 2002
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1006/jcss.2001.1815
cardinality reduction; computational path; function refinement; narrowing-gap condition; non-deterministic polynomial time; NP functions; NP machines; solution reduction
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A low and a high hierarchy within NP
- On self-reducibility and weak P-selectivity
- Qualitative relativizations of complexity classes
- A uniform approach to define complexity classes
- Symmetric alternation captures BPP
- A hierarchy based on output multiplicity
- A taxonomy of complexity classes of functions
- Functions computable with limited access to NP
- More on BPP and the polynomial-time hierarchy
- Easy sets and hard certificate schemes
- A complexity theory for feasible closure properties
- A note on parallel queries and the symmetric-difference hierarchy.
- Quantitative Relativizations of Complexity Classes
- The Boolean Hierarchy I: Structural Properties
- New Collapse Consequences of NP Having Small Circuits
- Query Order
- RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
- Computing Solutions Uniquely Collapses the Polynomial Hierarchy
