dichotomy for holant* problems of boolean domain

	*dichotomy for holant problems of boolean domain**
	Cai Jin-Yi; Lu Pinyan; Xia Mingji
	2011
会议名称	22nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011
会议录名称	Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
页码	1714-1728
会议日期	23-Jan
会议地点	San Francisco, CA, United states
收录类别	EI
出版地	United States
ISBN	9780898719932
部门归属	(1) University of Wisconsin-Madison, United States; (2) Microsoft Research Asia, China; (3) Institute of Software, Chinese Academy of Sciences, China
摘要	Holant problems are a general framework to study counting problems. Both counting Constraint Satisfaction Problems (#CSP) and graph homomorphisms are special cases. We prove a complexity dichotomy theorem for Holant* (F), where F is a set of constraint functions on Boolean variables and output complex values. The constraint functions need not be symmetric functions. We identify four classes of problems which are polynomial time computable; all other problems are proved to be #P-hard. The main proof technique arid indeed the formulation of the theorem use holographic algorithms and reductions. By considering these counting problems over the complex domain, we discover surprising new tractable classes, which are associated with isotropic vectors, i.e., a (lion-zero) vector whose inner product with itself is zero.
关键词	Algorithms Polynomial Approximation Theorem Proving
主办者	ACM Spec. Interest Group. Algorithms Comput. Theory (SIGACT); SIAM Activity Group on Discrete Mathematics
内容类型	会议论文
URI标识	http://ir.iscas.ac.cn/handle/311060/14323
专题	基础软件与系统重点实验室
推荐引用方式 GB/T 7714	Cai Jin-Yi,Lu Pinyan,Xia Mingji. dichotomy for holant* problems of boolean domain[C]. United States,2011:1714-1728.

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
dichotomy for holant（366KB）			开放获取	--	请求全文