2024/03/21 by Liu, Yin
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2403.14150
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.