کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332592 | 687692 | 2005 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An algorithm for the satisfiability problem of formulas in conjunctive normal form
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: An algorithm for the satisfiability problem of formulas in conjunctive normal form An algorithm for the satisfiability problem of formulas in conjunctive normal form](/preview/png/10332592.png)
چکیده انگلیسی
We consider the satisfiability problem on Boolean formulas in conjunctive normal form. We show that a satisfying assignment of a formula can be found in polynomial time with a success probability of 2ân(1â1/(1+logm)), where n and m are the number of variables and the number of clauses of the formula, respectively. If the number of clauses of the formulas is bounded by nc for some constant c, this gives an expected run time of O(p(n)·2n(1â1/(1+clogn))) for a polynomial p.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Algorithms - Volume 54, Issue 1, January 2005, Pages 40-44
Journal: Journal of Algorithms - Volume 54, Issue 1, January 2005, Pages 40-44
نویسندگان
Rainer Schuler,