کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
9657817 | 690045 | 2005 | 18 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Subtractive reductions and complete problems for counting complexity classes
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Subtractive reductions and complete problems for counting complexity classes Subtractive reductions and complete problems for counting complexity classes](/preview/png/9657817.png)
چکیده انگلیسی
We introduce and investigate a new type of reductions between counting problems, which we call subtractive reductions. We show that the main counting complexity classes #P, #NP, as well as all higher counting complexity classes #·ΠkP,k⩾2, are closed under subtractive reductions. We then pursue problems that are complete for these classes via subtractive reductions. We focus on the class #NP (which is the same as the class #·coNP) and show that it contains natural complete problems via subtractive reductions, such as the problem of counting the minimal models of a Boolean formula in conjunctive normal form and the problem of counting the cardinality of the set of minimal solutions of a homogeneous system of linear Diophantine inequalities.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 340, Issue 3, 31 August 2005, Pages 496-513
Journal: Theoretical Computer Science - Volume 340, Issue 3, 31 August 2005, Pages 496-513
نویسندگان
Arnaud Durand, Miki Hermann, Phokion G. Kolaitis,