Theory and Applications of Satisfiability Testing: 8th International Conference, SAT 2005, St Andrews, UK, June 19-23, 2005. Proceedings

هشتمین کنفرانس بین المللی تئوری و کاربردهای تست توانایی رضایت (SAT2005) یک انجمن بین المللی برای مرکز تحقیقات بیشتر در مورد مشکل رضایتمندی (SAT) ارائه کرد. SAT مشکل کلاسیک تعیین این است که آیا یک فرمول گزاره دارای تخصیص صدق رضایت بخش است یا خیر. این اولین مشکلی بود که کوک نشان داد NP-complete است. با وجود ماهیت به ظاهر تخصصی آن، آزمون رضایتمندی در طیف گسترده ای از رشته های مختلف، هم از نظر عملی و هم از نظر نظری، بسیار مفید است. برای مثال، کار بر روی SAT به ارائه بینش در مورد مسائل اساسی مختلف در محاسبات ادامه می‌دهد، و فناوری حل SAT تا جایی پیشرفت کرده است که به مؤثرترین روش برای حل تعدادی از مسائل عملی تبدیل شده است. مجموعه کنفرانس های SAT کنفرانس های چند رشته ای هستند که برای گرد هم آوردن محققان از رشته های مختلف علاقه مند به SAT طراحی شده اند. موضوعات مورد علاقه شامل، اما نه محدود به: سیستم های اثبات و اثبات c- پیچیدگی; الگوریتم های جستجو و اکتشافی؛ تجزیه و تحلیل الگوریتم ها؛ نظریه های فراتر از گزاره نمونه های سخت و فرمول های تصادفی؛ رمزگذاری مشکل؛ - کاربردهای صنعتی؛ حل کننده ها و سایر ابزارها این جلد شامل مقالات پذیرفته شده برای ارائه در SAT 2005 است. این کنفرانس رکورد 73 ارسالی را به خود اختصاص داد. از این تعداد، 26 مقاله برای ارائه در برنامه فنی پذیرفته شد. علاوه بر این، 16 نفر به عنوان مقالات کوتاهتر پذیرفته شدند و به عنوان پوستر در طول برنامه فنی ارائه شدند.

The 8th International Conference on Theory and Applications of Satis?ability Testing(SAT2005)providedaninternationalforumforthemostrecentresearch on the satis?ablity problem (SAT). SAT is the classic problem of determining whether or not a propositional formula has a satisfying truth assignment. It was the ?rst problem shown by Cook to be NP-complete. Despite its seemingly specialized nature, satis?ability testing has proved to extremely useful in a wide range of di?erent disciplines, both from a practical as well as from a theoretical point of view. For example, work on SAT continues to provide insight into various fundamental problems in computation, and SAT solving technology has advanced to the point where it has become the most e?ective way of solving a number of practical problems. The SAT series of conferences are multidisciplinary conferences intended to bring together researchers from various disciplines who are interested in SAT. Topics of interest include, but are not limited to: proof systems and proof c- plexity; search algorithms and heuristics; analysis of algorithms; theories beyond the propositional; hard instances and random formulae; problem encodings; - dustrial applications; solvers and other tools. This volume contains the papers accepted for presentation at SAT 2005. The conference attracted a record number of 73 submissions. Of these, 26 papers were accepted for presentation in the technical programme. In addition, 16 - pers were accepted as shorter papers and were presented as posters during the technicalprogramme.Theacceptedpapersandposterpaperscoverthefullrange of topics listed in the call for papers.