Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
arXiv:2411.10453v1h-index: 11FROM
Originality Synthesis-oriented
AI Analysis
This work addresses theoretical computer scientists studying complexity and optimization, but it appears incremental as it builds on existing reduction concepts.
The authors tackled the problem of understanding phase transitions in combinatorial optimization by defining two types of geometry-preserving reductions between constraint satisfaction problems and other NP-search problems, providing examples and counterexamples to illustrate these reductions.
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.