کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418837 | 681720 | 2009 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Using clausal graphs to determine the computational complexity of k-bounded positive one-in-three SAT
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The one-in-three SAT problem is known to be NP -complete even in the absence of negated variables [T.J. Schaefer, The complexity of satisfiability problems, in: Proceedings of the 10th Annual ACM Symposium on Theory of Computing, ACM, New York, 1978, pp. 216–226], a variant known as positive (or monotone) one-in-three SAT. In this note, we use clausal graphs to investigate a further restriction: kk-bounded positive one-in-three SAT (kkBP one-in-three SAT), in which each variable occurs in no more than kk clauses. We show that for k=2k=2, kk BP one-in-three SAT is in the polynomial complexity class PP, while for all k>2k>2, it is NP -complete, providing another way of exploring the boundary between classes PP and NP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1655–1659
Journal: Discrete Applied Mathematics - Volume 157, Issue 7, 6 April 2009, Pages 1655–1659
نویسندگان
Richard Denman, Stephen Foster,