Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2407.09097 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866918278023086080 |
|---|---|
| author | Lichter, Moritz Pago, Benedikt |
| author_facet | Lichter, Moritz Pago, Benedikt |
| contents | We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tractable and not even all Maltsev CSPs. This rules them out as candidates for a universal polynomial-time CSP algorithm. The algorithms are $\mathbb{Z}$-affine $k$-consistency, BLP+AIP, BA$^{k}$, and CLAP. We thereby answer a question by Brakensiek, Guruswami, Wrochna, and Živný whether BLP+AIP solves all tractable CSPs in the negative. We also refute a conjecture by Dalmau and Opršal (LICS 2024) that every CSP is either solved by $\mathbb{Z}$-affine $k$-consistency or admits a Datalog reduction from 3-colorability. For the cohomological $k$-consistency algorithm, that is also based on affine relaxations, we show that it correctly solves our counterexample but fails on an NP-complete template. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_09097 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems Lichter, Moritz Pago, Benedikt Computational Complexity We show that various recent algorithms for finite-domain constraint satisfaction problems (CSP), which are based on solving their affine integer relaxations, do not solve all tractable and not even all Maltsev CSPs. This rules them out as candidates for a universal polynomial-time CSP algorithm. The algorithms are $\mathbb{Z}$-affine $k$-consistency, BLP+AIP, BA$^{k}$, and CLAP. We thereby answer a question by Brakensiek, Guruswami, Wrochna, and Živný whether BLP+AIP solves all tractable CSPs in the negative. We also refute a conjecture by Dalmau and Opršal (LICS 2024) that every CSP is either solved by $\mathbb{Z}$-affine $k$-consistency or admits a Datalog reduction from 3-colorability. For the cohomological $k$-consistency algorithm, that is also based on affine relaxations, we show that it correctly solves our counterexample but fails on an NP-complete template. |
| title | Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2407.09097 |