Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)

Reductions are the fundamental tool of computational complexity. They allow classification of computational problems into families (somewhat resembling those in biology), with problems in the same class sharing common features (in particular NP-complete problems being isomorphic versions of a single problem, if we believe that the Berman-Hartmanis conjecture [6] holds). A significant concern in the literature on complexity-theoretic reductions is to make the theory of reductions more predictive. This means that we should aim to better connect the structural properties of the two problems that the given reduction is connecting. For instance the notion of pasimonious reduction attempts to preserve the total number of solutions between instances.