Reducing the number of solutions of NP functions

DOI10.1006/JCSS.2001.1815MaRDI QIDQ1608321zbMATH OpenOpenAlexFDO

Authors Lane A. Hemaspaandra, 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

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)

Recommendations

• scientific article; zbMATH DE number 1759426
• scientific article; zbMATH DE number 3889514
• scientific article; zbMATH DE number 915981
• scientific article; zbMATH DE number 4126690
• Nonuniform reductions and NP-completeness
• Nonuniform reductions and NP-completeness
• On reductions of NP sets to sparse sets
• scientific article; zbMATH DE number 1072533
• Approximate solution of NP optimization problems
• scientific article; zbMATH DE number 1944142

Cites work

• scientific article; zbMATH DE number 1072533 (Why is no real title available?)
• scientific article; zbMATH DE number 1091107 (Why is no real title available?)
• scientific article; zbMATH DE number 1500515 (Why is no real title available?)
• scientific article; zbMATH DE number 1543293 (Why is no real title available?)
• scientific article; zbMATH DE number 1759419 (Why is no real title available?)
• scientific article; zbMATH DE number 1759433 (Why is no real title available?)
• A complexity theory for feasible closure properties
• A hierarchy based on output multiplicity
• A low and a high hierarchy within NP
• A note on parallel queries and the symmetric-difference hierarchy.
• A taxonomy of complexity classes of functions
• A uniform approach to define complexity classes
• Computing Solutions Uniquely Collapses the Polynomial Hierarchy
• Easy sets and hard certificate schemes
• Functions computable with limited access to NP
• More on BPP and the polynomial-time hierarchy
• New Collapse Consequences of NP Having Small Circuits
• On self-reducibility and weak P-selectivity
• Qualitative relativizations of complexity classes
• Quantitative Relativizations of Complexity Classes
• Query Order
• RELATIVIZABLE AND NONRELATIVIZABLE THEOREMS IN THE POLYNOMIAL THEORY OF ALGORITHMS
• Symmetric alternation captures BPP
• The Boolean Hierarchy I: Structural Properties

Cited in

(4)

• The consequences of eliminating NP solutions
• NP is as easy as detecting unique solutions
• scientific article; zbMATH DE number 1759426 (Why is no real title available?)
• scientific article; zbMATH DE number 4126690 (Why is no real title available?)

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

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