Journal
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Volume 78, Issue 2, Pages 681-688Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2011.12.002
Keywords
Counting; Constraint satisfaction; Complexity theory
Funding
- EPSRC
- NSERC
- EPSRC [EP/I011935/1, EP/I012087/1, EP/E062482/1] Funding Source: UKRI
- Engineering and Physical Sciences Research Council [EP/I012087/1, EP/I011935/1, EP/E062482/1] Funding Source: researchfish
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
