NONNEGATIVE WEIGHTED #CSP: AN EFFECTIVE COMPLEXITY DICHOTOMY

doi:10.1137/15M1032314

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

	NONNEGATIVE WEIGHTED #CSP: AN EFFECTIVE COMPLEXITY DICHOTOMY
	Cai, Jin-Yi 1; Chen, Xi 2; Lu, Pinyan 3
刊名	SIAM JOURNAL ON COMPUTING
	2016
卷号	45 期号:6 页码:2177-2198
关键词	constraint satisfaction problem counting problems complexity dichotomy
ISSN号	0097-5397
DOI	10.1137/15M1032314
英文摘要	We prove a complexity dichotomy theorem for counting constraint satisfaction problems (#CSPs) with nonnegative and algebraic weights. This caps a long series of important results on counting problems including counting unweighted and weighted graph homomorphisms and the celebrated dichotomy theorem for unweighted #CSPs. Our dichotomy theorem gives a succinct criterion for tractability. If a set F of constraint functions satisfies this criterion, then the problem #CSP(F) defined by F is solvable in polynomial time; if F does not satisfy this criterion, then the problem is #P -hard. Furthermore, we show that the question of whether a given F satisfies the criterion or not is decidable in NP. Surprisingly, our tractability criterion is simpler than the previous criteria for the more restricted classes of counting problems, although when specialized to those classes, they are logically equivalent. Our proof mainly uses linear algebra and represents a departure from universal algebra, the dominant methodology in recent years for the study of #CSPs on large domains.
WOS研究方向	Computer Science ; Mathematics
语种	英语
出版者	SIAM PUBLICATIONS
WOS记录号	WOS:000391838800007
内容类型	期刊论文
源URL	[http://10.2.47.112/handle/2XS4QKH4/1374]
专题	上海财经大学
通讯作者	Cai, Jin-Yi
作者单位	1.Univ Wisconsin, Dept Comp Sci, 1210 W Dayton St, Madison, WI 53706 USA; 2.Columbia Univ, Dept Comp Sci, New York, NY 10027 USA; 3.Shanghai Univ Finance & Econ, Inst Theoret Comp Sci, Shanghai 200433, Peoples R China
推荐引用方式 GB/T 7714	Cai, Jin-Yi,Chen, Xi,Lu, Pinyan. NONNEGATIVE WEIGHTED #CSP: AN EFFECTIVE COMPLEXITY DICHOTOMY[J]. SIAM JOURNAL ON COMPUTING,2016,45(6):2177-2198.
APA	Cai, Jin-Yi,Chen, Xi,&Lu, Pinyan.(2016).NONNEGATIVE WEIGHTED #CSP: AN EFFECTIVE COMPLEXITY DICHOTOMY.SIAM JOURNAL ON COMPUTING,45(6),2177-2198.
MLA	Cai, Jin-Yi,et al."NONNEGATIVE WEIGHTED #CSP: AN EFFECTIVE COMPLEXITY DICHOTOMY".SIAM JOURNAL ON COMPUTING 45.6(2016):2177-2198.