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

Abstract

Motivated by phase transitions in combinatorial optimization problems, we define two kinds of geometry-preserving reductions between constraint satisfaction problems and other NP-search problems. We give a couple of examples and counterexamples for these reductions.

In Proceedings FROM 2024, arXiv:2410.23020. An extended version is under preparation and will also be posted on arXiv

References in corpus (8)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Pairs of SAT Assignment in Random Boolean Formulae
• Belief propagation for graph partitioning
• Local consistency as a reduction between constraint satisfaction problems
• The replica symmetric phase of random constraint satisfaction problems
• Computational Complexity and Phase Transitions