امیراحمد نیری - مربی گروه علوم کامپیوتر، دانشگاه سلمان فارسی کازرون ،کازرون ،ایران

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

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