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 条

[31] Structural tractability of enumerating CSP solutions
Greco, Gianluigi
Scarcello, Francesco
CONSTRAINTS, 2013, 18 (01) : 38 - 74
[32] A Comparison between SAT and CSP Techniques
Hachemi Bennaceur
Constraints, 2004, 9 : 123 - 138
[33] A Dichotomy for Real Weighted Holant Problems
Huang, Sangxia
Lu, Pinyan
COMPUTATIONAL COMPLEXITY, 2016, 25 (01) : 255 - 304
[34] THE COMPLEXITY OF GENERAL-VALUED CSPs
Kolmogorov, Vladimir
Krokhin, Andrei
Rolinek, Michal
SIAM JOURNAL ON COMPUTING, 2017, 46 (03) : 1087 - 1110
[35] Constraints, Graphs, Algebra, Logic, and Complexity
Vardi, Moshe Y.
IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2011), 2011, 13 : 3 - 3
[36] On the relations between SAT and CSP enumerative algorithms
Génisson, R
Jégou, P
DISCRETE APPLIED MATHEMATICS, 2000, 107 (1-3) : 27 - 40
[37] Feasible distributed CSP models for scheduling problems
Salido, Miguel A.
Giret, Adriana
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2008, 21 (05) : 723 - 732
[38] From Marriages to Coalitions: A Soft CSP Approach
Bistarelli, Stefano
Foley, Simon
O'Sullivan, Barry
Santini, Francesco
RECENT ADVANCES IN CONSTRAINTS, 2009, 5655 : 1 - +
[39] The approximability of three-valued MAX CSP
Jonsson, P
Klasson, M
Krokhin, A
SIAM JOURNAL ON COMPUTING, 2006, 35 (06) : 1329 - 1349
[40] The Foundations of Complexity, the Complexity of Foundations
Cudworth, Erika
Hobden, Stephen
PHILOSOPHY OF THE SOCIAL SCIENCES, 2012, 42 (02) : 163 - 187

← 1 2 3 4 5 →