English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

Dichotomy for Holant Problems with a Function on Domain Size 3

MPS-Authors
/persons/resource/persons127523

Xia,  Mingji
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)

arXiv:1207.2354.pdf
(Preprint), 830KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Cai, J.-Y., Lu, P., & Xia, M. (2012). Dichotomy for Holant Problems with a Function on Domain Size 3. Retrieved from http://arxiv.org/abs/1207.2354.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0015-8809-F
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.