The complexity of weighted and unweighted #CSP
classification
💻 cs.CC
keywords
complexityreductionsunweightedweightedappliedapproximateclasscomputation
read the original 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 a recent dichotomy for unweighted #CSP can be extended to rational-weighted #CSP.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.