Witness-Isomorphic Reductions and the Local Search Problem

摘要

We study witness-isomorphic reductions, a type of structure-preserving reductionbetween NP decision problems. We show that witness-isomorphic reductions can be used in a uniform approach to the local search problem.