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 条

[21] Holant Problems and Counting CSP
Cai, Jin-Yi
Lu, Pinyan
Xia, Mingji
STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2009, : 715 - 724
[22] CSP DICHOTOMY FOR SPECIAL POLYADS
Barto, Libor
Bulin, Jakub
INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2013, 23 (05) : 1151 - 1174
[23] Backdoors to Tractable Valued CSP
Ganian, Robert
Ramanujan, M. S.
Szeider, Stefan
PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING, CP 2016, 2016, 9892 : 233 - 250
[24] Combining Treewidth and Backdoors for CSP
Ganian, Robert
Ramanujan, M. S.
Szeider, Stefan
34TH SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2017), 2017, 66
[25] Backdoors into heterogeneous classes of SAT and CSP
Gaspers, Serge
Misra, Neeldhara
Ordyniak, Sebastian
Szeider, Stefan
Zivny, Stanislav
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2017, 85 : 38 - 56
[26] A Configurational Approach to CSP Selection and Rejection
Hossain, Mohammad Alamgir
Sabani, Alvedi
Lokuge, Sachithra
Boo, Yee Ling
Kaisar, Shahriar
Menon, Preetha
JOURNAL OF COMPUTER INFORMATION SYSTEMS, 2024,
[27] Bounded Degree Nonnegative Counting CSP
Cai, Jin-Yi
Szabo, Daniel P.
ACM TRANSACTIONS ON COMPUTATION THEORY, 2024, 16 (02)
[28] A comparison between SAT and CSP techniques
Bennaceur, H
CONSTRAINTS, 2004, 9 (02) : 123 - 138
[29] A comparison of structural CSP decomposition methods
Gottlob, G
Leone, N
Scarcello, F
ARTIFICIAL INTELLIGENCE, 2000, 124 (02) : 243 - 282
[30] CSP Gaps and Reductions in the Lasserre Hierarchy
Tulsiani, Madhur
STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, 2009, : 303 - 312

← 1 2 3 4 5 →