| holographic reduction: a domain changed application and its partial converse theorems |
| Xia Mingji
|
| 2010
|
| 会议名称 | 37th International Colloquium on Automata, Languages and Programming, ICALP 2010
|
| 会议录名称 | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
|
| 页码 | 666-677
|
| 会议日期 | 44018
|
| 会议地点 | Bordeaux, France
|
| 收录类别 | ei
|
| 出版地 | Germany
|
| ISSN | 3029743
|
| ISBN | 3642141641
|
| 部门归属 | (1) State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, P.O. Box 8718, Beijing 100190, China
|
| 摘要 | Holographic reductions between some Holant problems and some #CSP(H d ) problems are built, where H d is some complex value binary function. By the complexity of these Holant problems, for each integer d≥2, #CSP(H d ) is in P when each variables appears at most d times, while it is #P-hard when each variables appears at most d+1 times. #CSP(H d ) counts weighted summation of graph homomorphisms from input graph G to graph H d , and the maximum occurrence of variables is the maximum degree of G. We conjecture 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 proved that the converse of holographic reduction holds for some classes of problems. © 2010 Springer-Verlag Berlin Heidelberg. |
| 关键词 | Linguistics
|
| 主办者 | CEA; Communaute Urbaine de Bordeaux; Conseil Regional dAquitaine; GDR Informatique Mathmatique (CNRS); INRIA; Total
|
| 语种 | 英语
|
| 内容类型 | 会议论文
|
| URI标识 | http://ir.iscas.ac.cn/handle/311060/8790
|
| 专题 | 2010软件所会议论文
|
推荐引用方式
GB/T 7714 |
Xia Mingji. holographic reduction: a domain changed application and its partial converse theorems[C]. Germany,2010:666-677.
|
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论