hide
Free keywords:
Computer Science, Computational Complexity, cs.CC
Abstract:
Holant problems are a general framework to study the algorithmic complexity
of counting problems. Both counting constraint satisfaction problems and graph
homomorphisms are special cases. All previous results of Holant problems are
over the Boolean domain. In this paper, we give the first dichotomy theorem for
Holant problems for domain size $>2$. We discover unexpected tractable families
of counting problems, by giving new polynomial time algorithms. This paper also
initiates holographic reductions in domains of size $>2$. This is our main
algorithmic technique, and is used for both tractable families and hardness
reductions. The dichotomy theorem is the following: For any complex-valued
symmetric function ${\bf F}$ with arity 3 on domain size 3, we give an explicit
criterion on ${\bf F}$, such that if ${\bf F}$ satisfies the criterion then the
problem ${\rm Holant}^*({\bf F})$ is computable in polynomial time, otherwise
${\rm Holant}^*({\bf F})$ is #P-hard.
