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

Gabriel Istrate

Motivated by phase transitions in combinatorial optimization problems, we define two kinds of geometry-preserving reductions between constraint satisfaction problems and other NP-s…