Discrete Homotopy and Promise Constraint Satisfaction Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914180226875392 |
|---|---|
| author | Beikmohammadi, Arash Bulatov, Andrei A. |
| author_facet | Beikmohammadi, Arash Bulatov, Andrei A. |
| contents | The Promise Constraint Satisfaction Problem (PCSP for short) is a generalization of the well-studied Constraint Satisfaction Problem (CSP). The PCSP has its roots in such classic problems as the Approximate Graph Coloring and the $(1+\varepsilon)$-Satisfiability problems. The area received much attention recently with multiple approaches developed to design efficient algorithms for restricted versions of the PCSP, and to prove its hardness.
One such approach uses methods from Algebraic Topology to relate the complexity of the PCSP to the structure of the fundamental group of certain topological spaces. In this paper, we attempt to develop a discrete analog of this approach by replacing topological structures with combinatorial constructions and some basic group-theoretic concepts. We consider the `one-dimensional' case of the approach. We introduce and prove the basics of the framework, show how it is related to the complexity of the PCSP, and obtain several hardness results, including the existing ones, as applications of our approach. The main hope, however, is that this discrete variant of the topological approach can be generalized to the `multi-dimensional' case needed for further progress. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_05120 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Discrete Homotopy and Promise Constraint Satisfaction Problem Beikmohammadi, Arash Bulatov, Andrei A. Computational Complexity Logic in Computer Science The Promise Constraint Satisfaction Problem (PCSP for short) is a generalization of the well-studied Constraint Satisfaction Problem (CSP). The PCSP has its roots in such classic problems as the Approximate Graph Coloring and the $(1+\varepsilon)$-Satisfiability problems. The area received much attention recently with multiple approaches developed to design efficient algorithms for restricted versions of the PCSP, and to prove its hardness. One such approach uses methods from Algebraic Topology to relate the complexity of the PCSP to the structure of the fundamental group of certain topological spaces. In this paper, we attempt to develop a discrete analog of this approach by replacing topological structures with combinatorial constructions and some basic group-theoretic concepts. We consider the `one-dimensional' case of the approach. We introduce and prove the basics of the framework, show how it is related to the complexity of the PCSP, and obtain several hardness results, including the existing ones, as applications of our approach. The main hope, however, is that this discrete variant of the topological approach can be generalized to the `multi-dimensional' case needed for further progress. |
| title | Discrete Homotopy and Promise Constraint Satisfaction Problem |
| topic | Computational Complexity Logic in Computer Science |
| url | https://arxiv.org/abs/2512.05120 |