Loading...
Please wait, while we are loading the content...
Similar Documents
Dichotomy for holant* problems with a function on domain size 3 (2012).
| Content Provider | CiteSeerX |
|---|---|
| Author | Cai, Jin-Yi Lu, Pinyan Xia, Mingji |
| 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 F with arity 3 on domain size 3, we give an explicit criterion on F, such that if F satisfies the criterion then the problem Holant∗(F) is computable in polynomial time, otherwise Holant∗(F) is #P-hard. |
| File Format | |
| Publisher Date | 2012-01-01 |
| Access Restriction | Open |
| Subject Keyword | Holant Problem Domain Size Tractable Family New Polynomial Time Algorithm Complex-valued Symmetric Function Special Case Main Algorithmic Technique Constraint Satisfaction Problem Holographic Reduction General Framework Hardness Reduction Polynomial Time Dichotomy Theorem Problem Holant Explicit Criterion Algorithmic Complexity Boolean Domain First Dichotomy Theorem Previous Result Graph Homomorphism |
| Content Type | Text |
| Resource Type | Article |
