The complexity of weighted and unweighted #CSP

被引：27

作者：

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

共 21 条

[1] The complexity of weighted Boolean #CSP with mixed signs [J].

Bulatov, Andrei ;

Dyer, Martin ;

Goldberg, Leslie Ann ;

Jalsenius, Markus ;

Richerby, David .

THEORETICAL COMPUTER SCIENCE, 2009, 410 (38-40) :3949-3961

[2]

Bulatov AA, 2008, LECT NOTES COMPUT SC, V5125, P646, DOI 10.1007/978-3-540-70575-8_53

[3] Towards a dichotomy theorem for the counting constraint satisfaction problem [J].

Bulatov, Andrei A. ;

Dalmau, Victor .

INFORMATION AND COMPUTATION, 2007, 205 (05) :651-678

[4] Non-negativelyWeighted #CSP: An Effective Complexity Dichotomya [J].

Cai, Jin-Yi ;

Chen, Xi ;

Lu, Pinyan .

2011 IEEE 26TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 2011, :45-54

[5] A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Non-negative Weights [J].

Cai, Jin-Yi ;

Chen, Xi .

2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, :437-446

[6]

Cai JY, 2010, LECT NOTES COMPUT SC, V6198, P275, DOI 10.1007/978-3-642-14165-2_24

[7]

Cai JY, 2009, ACM S THEORY COMPUT, P715

[8] Complexity of generalized satisfiability counting problems [J].

Creignou, N ;

Hermann, M .

INFORMATION AND COMPUTATION, 1996, 125 (01) :1-12

[9] The relative complexity of approximate counting problems [J].

Dyer, M ;

Goldberg, LA ;

Greenhill, C ;

Jerrum, M .

ALGORITHMICA, 2004, 38 (03) :471-500

[10]

Dyer M, 2000, RANDOM STRUCT ALGOR, V17, P260, DOI 10.1002/1098-2418(200010/12)17:3/4<260::AID-RSA5>3.0.CO

← 1 2 3 →