HOLOGRAPHIC ALGORITHMS WITH MATCHGATES CAPTURE PRECISELY TRACTABLE PLANAR #CSP

doi:10.1137/16M1073984

CORC > 上海财经大学 > 上海财经大学

	HOLOGRAPHIC ALGORITHMS WITH MATCHGATES CAPTURE PRECISELY TRACTABLE PLANAR #CSP
	Cai, Jin-Yi 1; Lu, Pinyan 2; Xia, Mingji 3
刊名	SIAM JOURNAL ON COMPUTING
	2017
卷号	46 期号:3 页码:853-889
关键词	holographic algorithms counting problems #P dichotomy theorems
ISSN号	0097-5397
DOI	10.1137/16M1073984
英文摘要	Valiant introduced matchgate computation and holographic algorithms. A number of seemingly exponential time problems can be solved by this novel algorithmic paradigm in polynomial time. We show that, in a very strong sense, matchgate computations and holographic algorithms based on them provide a universal methodology to a broad class of counting problems studied in the statistical physics community for decades. They capture precisely those problems which are #P-hard on general graphs but computable in polynomial time on planar graphs. More precisely, we prove complexity dichotomy theorems in the framework of counting CSP problems. The local constraint functions take Boolean inputs and can be arbitrary real-valued symmetric functions. We prove that every problem in this class belongs to precisely three categories: (1) those which are tractable (i.e., polynomial time computable) on general graphs, or (2) those which are #P-hard on general graphs but tractable on planar graphs, or (3) those which are #P-hard even on planar graphs. The classification criteria are explicit. Moreover, problems in category (2) are tractable on planar graphs precisely by holographic algorithms with matchgates.
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SIAM PUBLICATIONS
WOS记录号	WOS:000404774300001
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/1095]
专题	上海财经大学
通讯作者	Lu, Pinyan
作者单位	1.Univ Wisconsin, Dept Comp Sci, 1210 W Dayton St, Madison, WI 53706 USA; 2.Shanghai Univ Finance & Econ, Shanghai, Peoples R China; 3.Univ Chinese Acad Sci, Chinese Acad Sci, State Key Lab Comp Sci, Inst Software, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Cai, Jin-Yi,Lu, Pinyan,Xia, Mingji. HOLOGRAPHIC ALGORITHMS WITH MATCHGATES CAPTURE PRECISELY TRACTABLE PLANAR #CSP[J]. SIAM JOURNAL ON COMPUTING,2017,46(3):853-889.
APA	Cai, Jin-Yi,Lu, Pinyan,&Xia, Mingji.(2017).HOLOGRAPHIC ALGORITHMS WITH MATCHGATES CAPTURE PRECISELY TRACTABLE PLANAR #CSP.SIAM JOURNAL ON COMPUTING,46(3),853-889.
MLA	Cai, Jin-Yi,et al."HOLOGRAPHIC ALGORITHMS WITH MATCHGATES CAPTURE PRECISELY TRACTABLE PLANAR #CSP".SIAM JOURNAL ON COMPUTING 46.3(2017):853-889.