A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914264034312192 |
|---|---|
| author | Bodirsky, Manuel Bonnet, Édouard Semanišinová, Žaneta |
| author_facet | Bodirsky, Manuel Bonnet, Édouard Semanišinová, Žaneta |
| contents | We study the complexity of the valued constraint satisfaction problem (VCSP) for every valued structure with the domain ${\mathbb Q}$ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classical) constraint satisfaction problem: a relational structure is preserved by all order-preserving bijections if and only if all its relations have a first-order definition in $({\mathbb Q};<)$, and the CSPs for such structures are called temporal CSPs. Many optimization problems that have been studied intensively in the literature can be phrased as a temporal VCSP. We prove that a temporal VCSP is in P, or NP-complete. Our analysis uses the concept of fractional polymorphisms. This is the first dichotomy result for VCSPs over infinite domains which is complete in the sense that it treats all valued structures with a given automorphism group. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07285 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems Bodirsky, Manuel Bonnet, Édouard Semanišinová, Žaneta Logic Computational Complexity 68Q25, 08A70 F.4.1; F.2.2 We study the complexity of the valued constraint satisfaction problem (VCSP) for every valued structure with the domain ${\mathbb Q}$ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classical) constraint satisfaction problem: a relational structure is preserved by all order-preserving bijections if and only if all its relations have a first-order definition in $({\mathbb Q};<)$, and the CSPs for such structures are called temporal CSPs. Many optimization problems that have been studied intensively in the literature can be phrased as a temporal VCSP. We prove that a temporal VCSP is in P, or NP-complete. Our analysis uses the concept of fractional polymorphisms. This is the first dichotomy result for VCSPs over infinite domains which is complete in the sense that it treats all valued structures with a given automorphism group. |
| title | A Complexity Dichotomy for Temporal Valued Constraint Satisfaction Problems |
| topic | Logic Computational Complexity 68Q25, 08A70 F.4.1; F.2.2 |
| url | https://arxiv.org/abs/2409.07285 |