کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430103 | 687798 | 2012 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
The complexity of weighted and unweighted #CSP
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: The complexity of weighted and unweighted #CSP The complexity of weighted and unweighted #CSP](/preview/png/430103.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 78, Issue 2, March 2012, Pages 681–688
Journal: Journal of Computer and System Sciences - Volume 78, Issue 2, March 2012, Pages 681–688
نویسندگان
Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby,