کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10320266 | 658375 | 2010 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Extended clause learning
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The past decade has seen clause learning as the most successful algorithm for SAT instances arising from real-world applications. This practical success is accompanied by theoretical results showing clause learning as equivalent in power to resolution. There exist, however, problems that are intractable for resolution, for which clause-learning solvers are hence doomed. In this paper, we present extended clause learning, a practical SAT algorithm that surpasses resolution in power. Indeed, we prove that it is equivalent in power to extended resolution, a proof system strictly more powerful than resolution. Empirical results based on an initial implementation suggest that the additional theoretical power can indeed translate into substantial practical gains.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 174, Issue 15, October 2010, Pages 1277-1284
Journal: Artificial Intelligence - Volume 174, Issue 15, October 2010, Pages 1277-1284
نویسندگان
Jinbo Huang,