| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 430103 | Journal of Computer and System Sciences | 2012 | 8 Pages |
Abstract
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.
► Proposes and applies a new class of reductions for weighted #CSP problems. ► The reductions can be applied to both exact and approximate computation. ► Shows equivalence for various classes of weighted #CSP problems. ► Extends the dichotomy for unweighted #CSP to rational-weighted #CSP. ► Shows that all weighted #CSP problems can be reduced to problems with one function.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby,