| Holographic Reduction: A Domain Changed Application and its Partial Converse Theorems |
| Download PDF |
| Mingji Xia. Holographic Reduction: A Domain Changed Application and its Partial Converse Theorems. International Journal of Software and Informatics, 2011,5(4):567~577 |
| Hits: 3725 |
| Download times: 2435 |
|
| Fund:This work is sponsored by the Chinese Academy of Sciences (CAS) start-up fund for CAS PresidentScholarship winner, the Hundred-Talent program of CAS under Angsheng Li, the Grand ChallengeProgram "Network Algorithms and Digital Information" of ISCAS, and NSFC 61003030. |
|
| Abstract:Holographic reductions between some Holant problems and some #CSP(Hd) problems are built, where Hd is some complex value binary function. By the complexity of these Holant problems, for each integer d >= 2, #CSP(Hd) is in P when each variable appears at most d times, while it is #P-hard when each variables appears at most d + 1 times. #CSP(Hd) counts weighted summation of graph homomorphisms from input graph G to graph Hd, and the maximum occurrence of variables is the maximum degree of G. We conjecture that the converse of holographic reduction holds for most of #Bi-restriction Constraint Satisfaction Problems, which can be regarded as a generalization of a known result about counting graph homomorphisms. It is shown that the converse of holographic reduction holds for some classes of problems. |
| keywords:holographic reduction graph homomorphism holant problem #CSP #BCSP |
| View Full Text View/Add Comment Download reader |
