Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917613998702592 |
|---|---|
| author | Yamakami, Tomoyuki |
| author_facet | Yamakami, Tomoyuki |
| contents | We study the computational complexity of counting constraint satisfaction problems (#CSPs) whose constraints assign complex numbers to Boolean inputs when the corresponding constraint hypergraphs are acyclic. These problems are called acyclic #CSPs or succinctly, #ACSPs. We wish to determine the computational complexity of all such #ACSPs when arbitrary unary constraints are freely available. Depending on whether we further allow or disallow the free use of the specific constraint XOR (binary disequality), we present two complexity classifications of the #ACSPs according to the types of constraints used for the problems. When XOR is freely available, we first obtain a complete dichotomy classification. On the contrary, when XOR is not available for free, we then obtain a trichotomy classification. To deal with an acyclic nature of constraints in those classifications, we develop a new technical tool called acyclic-T-constructibility or AT-constructibility, and we exploit it to analyze a complexity upper bound of each #ACSPs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_09145 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems Yamakami, Tomoyuki Computational Complexity Formal Languages and Automata Theory Symbolic Computation We study the computational complexity of counting constraint satisfaction problems (#CSPs) whose constraints assign complex numbers to Boolean inputs when the corresponding constraint hypergraphs are acyclic. These problems are called acyclic #CSPs or succinctly, #ACSPs. We wish to determine the computational complexity of all such #ACSPs when arbitrary unary constraints are freely available. Depending on whether we further allow or disallow the free use of the specific constraint XOR (binary disequality), we present two complexity classifications of the #ACSPs according to the types of constraints used for the problems. When XOR is freely available, we first obtain a complete dichotomy classification. On the contrary, when XOR is not available for free, we then obtain a trichotomy classification. To deal with an acyclic nature of constraints in those classifications, we develop a new technical tool called acyclic-T-constructibility or AT-constructibility, and we exploit it to analyze a complexity upper bound of each #ACSPs. |
| title | Complexity Classification of Complex-Weighted Counting Acyclic Constraint Satisfaction Problems |
| topic | Computational Complexity Formal Languages and Automata Theory Symbolic Computation |
| url | https://arxiv.org/abs/2403.09145 |