The complexity of weighted and unweighted #CSP

被引：26

作者：

Bulatov, Andrei ^{[2
]}

Dyer, Martin ^{[1
]}

Goldberg, Leslie Ann ^{[3
]}

Jalsenius, Markus ^{[4
]}

Jerrum, Mark ^{[5
]}

Richerby, David ^{[3
]}

机构：

[1] Univ Leeds, Sch Comp, Leeds LS2 9JT, W Yorkshire, England

[2] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada

[3] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England

[4] Univ Bristol, Dept Comp Sci, Bristol BS8 1UB, Avon, England

[5] Univ London, Sch Math Sci, London E1 4NS, England

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2012年 / 78卷 / 02期

基金：

英国工程与自然科学研究理事会; 加拿大自然科学与工程研究理事会;

关键词：

Counting; Constraint satisfaction; Complexity theory; DICHOTOMY;

D O I：

10.1016/j.jcss.2011.12.002

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We give some reductions among problems in (nonnegative) weighted #CSP which restrict the class of functions that needs to be considered in computational complexity studies. Our reductions can be applied to both exact and approximate computation. In particular, we show that the recent dichotomy for unweighted #CSP can be extended to rational-weighted #CSP. (C) 2011 Elsevier Inc. All rights reserved.

引用

页码：681 / 688

页数：8

共 50 条

[1] THE COMPLEXITY OF WEIGHTED BOOLEAN #CSP
Dyer, Martin
Goldberg, Leslie Ann
Jerrum, Mark
SIAM JOURNAL ON COMPUTING, 2009, 38 (05) : 1970 - 1986
[2] The complexity of weighted Boolean #CSP with mixed signs
Bulatov, Andrei
Dyer, Martin
Goldberg, Leslie Ann
Jalsenius, Markus
Richerby, David
THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) : 3949 - 3961
[3] Complexity of Counting CSP with Complex Weights
Cai, Jin-Yi
Chen, Xi
STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2012, : 909 - 919
[4] Quantum advantage and CSP complexity
Ciardo, Lorenzo
PROCEEDINGS OF THE 39TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS 2024, 2024,
[5] THE COMPLEXITY OF APPROXIMATING BOUNDED-DEGREE BOOLEAN #CSP
Dyer, Martin
Goldberg, Leslie Ann
Jalsenius, Markus
Richerby, David
27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010), 2010, 5 : 323 - 334
[6] Complexity of Counting CSP with Complex Weights
Cai, Jin-Yi
Chen, Xi
JOURNAL OF THE ACM, 2017, 64 (03)
[7] Solving weighted CSP by maintaining arc consistency
Larrosa, J
Schiex, T
ARTIFICIAL INTELLIGENCE, 2004, 159 (1-2) : 1 - 26
[8] The Complexity of Planar Boolean #CSP with Complex Weights
Guo, Heng
Williams, Tyson
AUTOMATA, LANGUAGES, AND PROGRAMMING, PT I, 2013, 7965 : 516 - 527
[9] The complexity of planar Boolean #CSP with complex weights
Guo, Heng
Williams, Tyson
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2020, 107 : 1 - 27
[10] A weighted CSP approach to cost-optimal planning
Cooper, Martin C.
de Roquemaurel, Marie
Regnier, Pierre
AI COMMUNICATIONS, 2011, 24 (01) : 1 - 29

← 1 2 3 4 5 →