Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910700614451200 |
|---|---|
| author | Istrate, Gabriel |
| author_facet | Istrate, Gabriel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_10453 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP) Istrate, Gabriel Computational Complexity Artificial Intelligence Discrete Mathematics F.2.2 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. |
| title | Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP) |
| topic | Computational Complexity Artificial Intelligence Discrete Mathematics F.2.2 |
| url | https://arxiv.org/abs/2411.10453 |