Reducing the number of solutions of NP functions

DOI10.1006/jcss.2001.1815zbMath1018.68032OpenAlexW2070660623MaRDI QIDQ1608321

Gerd Wechsung, Hemaspaandra, Lane A., Ogihara, Mitsunori

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

zbMATH Keywords

cardinality reductioncomputational pathfunction refinementnarrowing-gap conditionnon-deterministic polynomial timeNP functionsNP machinessolution reduction

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

The consequences of eliminating NP solutions

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

This page was built for publication: Reducing the number of solutions of NP functions