Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2508.11540 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909738011197440 |
|---|---|
| author | Delic, Dejan Marcoux, John |
| author_facet | Delic, Dejan Marcoux, John |
| contents | Constraint Satisfaction Problems (CSPs, for short) make up a class of problems with applications in many areas of computer science. The first classification of these problems was given by Schaeffer who showed that every CSP over the domain {0,1} is either in P or is NP-complete. More recently this was shown to hold for all CSPs over finite relational structures independently by Bulatov and Zhuk. Furthermore, they characterized the complexity based solely on the polymorphism algebra of the associated relational structure, building upon the deep connections between universal algebra and complexity theory. In this article we extend this and consider what happens if the instance forms a special type of relational core called a multisorted core. Our main result is that in this case the problem is reducible to computing the determinant of an integer valued matrix which places it in the complexity class DET, which is likely a strict subset of P. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_11540 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Constraint Satisfaction Problem Over Multisorted Cores Delic, Dejan Marcoux, John Computational Complexity Logic in Computer Science 68R Constraint Satisfaction Problems (CSPs, for short) make up a class of problems with applications in many areas of computer science. The first classification of these problems was given by Schaeffer who showed that every CSP over the domain {0,1} is either in P or is NP-complete. More recently this was shown to hold for all CSPs over finite relational structures independently by Bulatov and Zhuk. Furthermore, they characterized the complexity based solely on the polymorphism algebra of the associated relational structure, building upon the deep connections between universal algebra and complexity theory. In this article we extend this and consider what happens if the instance forms a special type of relational core called a multisorted core. Our main result is that in this case the problem is reducible to computing the determinant of an integer valued matrix which places it in the complexity class DET, which is likely a strict subset of P. |
| title | The Constraint Satisfaction Problem Over Multisorted Cores |
| topic | Computational Complexity Logic in Computer Science 68R |
| url | https://arxiv.org/abs/2508.11540 |