A combinatorial view of Holant problems on higher domains
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_ | 1866909219610951680 |
|---|---|
| author | Liu, Yin |
| author_facet | Liu, Yin |
| contents | On the Boolean domain, there is a class of symmetric signatures called ``Fibonacci gates'' for which a beautiful P-time combinatorial algorithm has been designed for the corresponding $\operatorname{Holant}$ problems.
In this work, I give a combinatorial view for $\operatorname{Holant}(\mathcal{F})$ problems on a domain of size 3 where $\mathcal{F}$ is a set of arity 3 functions with inputs taking values on the domain of size 3 and the functions share some common properties. The combinatorial view can also be extended to the domain of size 4.
Specifically, I extend the definition of "Fibonacci gates" to the domain of size 3 and the domain of size 4. Moreover, I give the corresponding combinatorial algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_14150 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A combinatorial view of Holant problems on higher domains Liu, Yin Computational Complexity Combinatorics On the Boolean domain, there is a class of symmetric signatures called ``Fibonacci gates'' for which a beautiful P-time combinatorial algorithm has been designed for the corresponding $\operatorname{Holant}$ problems. In this work, I give a combinatorial view for $\operatorname{Holant}(\mathcal{F})$ problems on a domain of size 3 where $\mathcal{F}$ is a set of arity 3 functions with inputs taking values on the domain of size 3 and the functions share some common properties. The combinatorial view can also be extended to the domain of size 4. Specifically, I extend the definition of "Fibonacci gates" to the domain of size 3 and the domain of size 4. Moreover, I give the corresponding combinatorial algorithms. |
| title | A combinatorial view of Holant problems on higher domains |
| topic | Computational Complexity Combinatorics |
| url | https://arxiv.org/abs/2403.14150 |