A combinatorial view of Holant problems on higher domains
Abstract
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 Holant problems.
In this work, I give a combinatorial view for Holant(F) problems on a domain of size 3 where 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.
In this work, I give a combinatorial view for Holant(F) problems on a domain of size 3 where 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.
