Local search algorithms for SAT: Worst-case analysis

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

2 اقتباسات (Scopus)

ملخص

Recent experiments demonstrated that local search algorithms (e.g. GSAT) are able to find satisfying assignments for many "hard" Boolean formulas. However, no non-trivial worst-case upper bounds were proved, although many such bounds of the form 2αn (α < 1 is a constant) are known for other SAT algorithms, e.g. resolution-like algorithms. In the present paper we prove such a bound for a local search algorithm, namely for CSAT. The class of formulas we consider covers most of DIMACS benchmarks, the satisfiability problem for this class of formulas is NP-complete.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithm Theory — SWAT 1998 - 6th Scandinavian Workshop on Algorithm Theory, Proceedings
المحررونStefan Arnborg, Lars Ivansson
الصفحات246-254
عدد الصفحات9
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1998
منشور خارجيًانعم
الحدث6th Scandinavian Workshop on Algorithm Theory, SWAT 1998 - Stockholm, السويد
المدة: ٨ يوليو ١٩٩٨١٠ يوليو ١٩٩٨

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت1432
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference6th Scandinavian Workshop on Algorithm Theory, SWAT 1998
الدولة/الإقليمالسويد
المدينةStockholm
المدة٨/٠٧/٩٨١٠/٠٧/٩٨

بصمة

أدرس بدقة موضوعات البحث “Local search algorithms for SAT: Worst-case analysis'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا