کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
10332592 687692 2005 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله 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
چکیده انگلیسی
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
نویسندگان
,