Reducing the number of solutions of NP functions

DOI10.1006/JCSS.2001.1815zbMATH Open1018.68032OpenAlexW2070660623MaRDI QIDQ1608321FDOQ1608321

Gerd Wechsung, Lane A. Hemaspaandra, 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)

Cites Work

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

Cited In (3)

• The consequences of eliminating NP solutions
• NP is as easy as detecting unique solutions
• Title not available (Why is that?)

Recommendations

• Approximate solution of NP optimization problems 👍 👎
• On reductions of NP sets to sparse sets 👍 👎
• Nonuniform reductions and NP-completeness 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

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)