K-SAT بعنوان یک سیستم پیچیده

دردو دهه اخیر مطالعه در مورد سیستم های پیچیده با هیجان و شدت دنبال می شود. پدیده های بسیاری در طبیعت وجود دارند که پیچیدگی آنها در چارچوب تیوری سیستم های پیچیده قابل تفسیر است. مساله k-SAT یکی از مهمترین مسایلی است که در علوم کامپیوتر مورد بررسی قرار می گیرد. علت توجه زیاد به این مساله آنست که ارایه راه حل سودمند برای حل آن(Polynomial Time Compleity)، راه را برای حل یکی از اساسی ترین مسایل باز در علم یعنی (P=NP) باز می نماید.در اینجا به بررسی پیچیدگی حل این مساله می پردازیم. نشان می دهیم که این پیچیدگی دقیقا با تحویل ناپذیری خصلت عمومی سیستم های پیچیده به رفتارهای محلی برابر است و بدین جهت دشواری این مساله باید بعنوان یک Emergent Phenomena مورد بررسی قرار گیرد.

Keywords:

ارضا پذیری , k-SAT , سیستم های پیچیده , پیدایش , تحویل ناپذیری , همبستگی , گشتاور اول