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 条

[41] On the Computational Complexity of Non-dictatorial Aggregation
Kirousis, Lefteris
Kolaitis, Phokion G.
Livieratos, John
RELATIONAL AND ALGEBRAIC METHODS IN COMPUTER SCIENCE, 2018, 11194 : 350 - 365
[42] Simplifying complexity: a review of complexity theory
Manson, SM
GEOFORUM, 2001, 32 (03) : 405 - 414
[43] From Holant to #CSP and Back: Dichotomy for Holantc Problems
Jin-Yi Cai
Sangxia Huang
Pinyan Lu
Algorithmica, 2012, 64 : 511 - 533
[44] Approximate Counting CSP Seen from the Other Side
Bulatov, Andrei A.
Zivny, Stanislav
ACM TRANSACTIONS ON COMPUTATION THEORY, 2020, 12 (02)
[45] The approximability of MAX CSP with fixed-value constraints
Deineko, Vladimir
Jonsson, Peter
Klasson, Mikael
Krokhin, Andrei
JOURNAL OF THE ACM, 2008, 55 (04)
[46] Every 2-csp Allows Nontrivial Approximation
Johan Håstad
computational complexity, 2008, 17 : 549 - 566
[47] EVERY 2-CSP ALLOWS NONTRIVIAL APPROXIMATION
Hastad, Johan
COMPUTATIONAL COMPLEXITY, 2008, 17 (04) : 549 - 566
[48] Learning and focusing strategies to improve ACO that solves CSP
Rojas-Morales, Nicolas
Riff, Maria-Cristina
Neveu, Bertrand
ENGINEERING APPLICATIONS OF ARTIFICIAL INTELLIGENCE, 2021, 105
[49] Sparsification of SAT and CSP Problems via Tractable Extensions
Lagerkvist, Victor
Wahlstrom, Magnus
ACM TRANSACTIONS ON COMPUTATION THEORY, 2020, 12 (02)
[50] From Holant to #CSP and Back: Dichotomy for Holantc Problems
Cai, Jin-Yi
Huang, Sangxia
Lu, Pinyan
ALGORITHMS AND COMPUTATION, PT I, 2010, 6506 : 253 - +

← 1 2 3 4 5 →