scientific article; zbMATH DE number 1048042

MaRDI QIDQ4348128zbMATH OpenFDO

Authors Lane A. Hemaspaandra, Leen Torenvliet, Sophie Fischer

Publication date 22 September 1997

zbMATH Keywords

decision proceduresNP completenesspolynomial-time computable functions

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Other degrees and reducibilities in computability and recursion theory (03D30) Analysis of algorithms and problem complexity (68Q25)

Review text

The authors study so-called witness-isomorphic reductions for NP decision problems. Different models of witness-isomorphic reduction are considered, and the relative power of the models is determined. The authors show that the reductions ``can be used in a uniform approach to the local search problem. For the entire collection see [Zbl 0865.00036].

Recommendations

• How easy is local search?
• A note on the complexity of local search problems
• The Complexity of Decision Versus Search
• On the hardness of global and local approximation

Cited in

(1)

• A note on \(\#\mathcal P\)-completeness of NP-witnessing relations

This page was built for publication:

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