17 Pages

Witness-Isomorphic Reductions and Local Search

WithSophie Fischer, Lane Hemaspaandra, Leen Torenvliet

We study witness-isomorphic reductions, a type of structure-preserving reduction between NP decision problems. We completely determine the relative power of the different models of witness-isomorphic reduction, and we show that witnessisomorphic reductions can be used in a uniform approach to the local search problem.