موضوع مقاله: قضیه کوک–لوین | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # قضیه کوک–لوین | مقدمه: در نظریه پیچیدگی رایانشی، قضیه کوک و لوین، که گاه قضیه کوک نیز خوانده می‌شود، نشان می‌دهد که مسئله صدق‌پذیری دودویی مسئله ای ان‌پی کامل است: الگوریتم نمی‌شناسیم که در زمانی کوتاه مسئله صدق‌پذیری را حل کند. | ## بخش 1: قضیه کوک–لوین | می‌توان این مسئله را به بسیاری دیگر از مسئله‌ها کاست و ان‌پی کامل بودنشان را نشان داد. از همین روی قضیهٔ کوک و لوین یکی از مهم‌ترین قضیه‌ها در زمینهٔ پیچیدگی رایانشی است. برآیهٔ (نتیچه‌ی) مهم این قضیه چنین است: اگر الگوریتمی با ییچیدگی زمانی چندجمله‌ای یکی از مسئله‌های دستهٔ ان‌پی کامل حل کند، همهٔ مسئله‌های دیگر را نیز می‌توان با پیچیدگی زمانی چندجمله‌ای حل نمود. این برآیه مسئله ای را به نام برابری پی و ان‌پی پیش می‌کشد که یکی از مهم‌ترین پرسشِ‌های بی‌پاسخ در دانش رایانه است. پیشینه پژوهندگان شوروی و آمریکا هم‌زمان نظریهٔ ان‌پی کامل را در پایان دههٔ ۱۹۶۰ و آغاز دههٔ ۱۹۷۰ پدیدآوردند. در آمریکا در سال ۱۹۷۱، استیون کوک مقالهٔ «پیچیدگی قضیهٔ آوین رویه‌ها» را در کنفرانس «انجمن نظریهٔ رایانش» چاپ کرد. به دنبالِ آن، ریچارد کارپ در سال ۱۹۷۲ مقالهٔ «کاهش میانِ مسئله‌های ترکیبی" را چاپ نمود. او به کمک نظریهٔ کوک فهرستی از ۲۱ مسئله ان‌پی-کامل کارپ را شناسایی کرد و نشان داد که چگونه در زمانی کوتاه می‌توان مسئله صدق‌پذیری دودویی را به این مسئله‌ها کاست. سپس، تیودور پی بیکر، جان گیل و روبرت ام سولووی در سال ۱۹۷۵ نشان دادند که حل مسئله‌های ان‌پی در ماشین سروش نیازمند زمانی نمایی است. در شوروی در سالِ ۱۹۶۹، ام دختیار نتیجه‌ای همانند نتیجهٔ بیکر، گیل و سولووی را به چاپ رسانید. گرچه پیش از این مقاله در گفت‌وگوها یاد شده بود و در چند سال پیش برای چاپ فرستاده شده بود. | ## بخش 2: قضیه کوک–لوین | دگرسانیِ رویکردِ لوین با رویکردِ کوک و کارپ در این است که لوین جست‌وجوهایی که راه حل را می‌جویند بررسی می‌کرد ولی کوک و کارپ بودنِ چنین راه‌حل‌هایی را بررسی می‌کردند. لوین ۶ مسئله جستجوی مسئله‌های همگانی (ان‌پی کامل) را شناساند و نشان داد که اگر الگوریتم جست‌وجویی با پیچیدگی زمانی چندجمله‌ای باشد که یکی از این مسئله‌ها را حل کند، می‌توان دیگر مسئله‌ها نیز با پیچیدگی زمانی چندجمله‌ای حل نمود. تعریف‌ها یک مسئله تصمیم ان‌پی خوانده می‌شود اگر بتوان آن را به کمک یک الگوریتم غیرقطعی در زمان چندجمله ای حل کرد. یک نمونه (instance) از مسئله صدق‌پذیری دودویی، یک عبارت منطقی است که شامل تعدادی عملگر و متغیر منطقیست. این مسئله می‌پرسد که آیا می‌توان متغیرهای عبارتی دودویی را چنان ارزش‌دهی کرد که عبارت ارزش درست بگیرد (که در این صورت عبارت صدق پذیر خوانده می‌شود). ایده هر مسئله تصمیمی در NP که داده شد، یک ماشین غیرقطعی بسازید که در زمانِ چندجمله‌ای مسئله را حل کند. سپس برای هر ورودی به آن ماشین، یک عبارت بولی بسازید که بگوید ورودی توسطِ ماشین پذیرفته و به درستی اجرا شده و ماشین پاسخ «بله» داده‌است. سپس عبارت می‌تواند راضی کننده باشد اگر و فقط اگر راهی برای اجرای صحیح و پاسخ «بله» سیستم وجود داشته باشد، بنابراین قابلیت راضی کردن عبارت ساخته شده معادل این پرسش است که آیا ماشین پاسخ «بله» می‌دهد یا خیر. بعدی نشان دادنِ اینکه هر مسئله NP می‌تواند به یک نمونه از مسئله رضایت دودویی کاهش یابد در یک زمان چندجمله‌ای! رضایت دودویی یک NP است چراکه هر مقدارِ دودوییِ تخصیص یافته به متغیرهای دودویی که ادعای رضایت بخش نمودنِ عبارت را دارند، می‌تواند در زمان چندجمله‌ای توسط یک ماشینِ تورینگِ قطعی، بررسی شوند. گفته شد، قابل بررسیِ در زمانِ چندجمله‌ای با ماشین تورینگ قطعی و حل شدنی در زمان چندجمله ای با ماشین تورینگ قطعی! | ## بخش 3: قضیه کوک–لوین | حالا فرض کنید مسئله داده شده می‌تواند توسط ماشین تورینگِ غیرقطعی حل شود "(M = (Q، Σ، s, F، δ"، جایی که Q مجموعه ای از وضعیت هاست، Σ نماد نوار، s ∈ Q وضعیت شروع، F ⊆ Q مجموعه وضعیت‌های پذیرفته شده، و "{δ: Q × Σ → Q × Σ × {−۱، +۱" مجموعه ای از تحول هاست. حالا فرض کنید M، یک نمونه از مسئله را در زمانِ (p(n پذیرش یا رد می‌کند جایی که n اندازه نمونه و p تابع چندجمله‌ای است. برای هر ورودی I، یک عبارت بولی که راضی کننده نیز هست به ان اختصاص می‌دهیم اگر و فقط اگر ماشینِ M، ورودیِ I را بپذیرد. بنابراین تبدیل؛ قطعاً در زمان چندجمله‌ای رخ می‌دهد چراکه تعداد بندها ۲ O(p(n می‌باشد و اندازه B برابر می‌باشد با: O(log(p(n p(n)۲) نتیجه اثبات نشان می‌دهد هر مسئله NP می‌تواند در یک زمانِ چندجمله ای به یک نمونه مسئله رضایت دودویی کاهش یابد (تبدیل شود) این یعنی، اگر مسئله رضایت بولی بتواند در زمان چندجمله ای توسط ماشینِ تورینگ غیرقطعی حل شود، پس تمامیِ مسئله‌های NP می‌تواند در زمانِ چندجمله ای حل شود و بنابراین کلاس پیچیدگی NP برابر با کلاس پیچیدگی P خواهد بود! «قابلیت کاهش میانِ مسئله‌های ترکیبی» که در آن ۲۱ ترکیبِ گوناگون و مسئله‌های نظریه گراف‌ها را نشان داد. روشِ کارپ برای اثباتِ کامل بودنِ مسئله‌هایش، بوسیله کاهش یک مسئله دیگر (که قبلاً ثابت شده NP کامل هست) به این مسئله صورت گرفت. برای مثال، برای نشان دادن اینکه ۳SAT (رضایت عبارت بولی ۳ متغیره) یک (رضایت عبارت بولی ۳ متغیره) یک NP کامل است، نشان داد که چگونه می‌توان یک نمونه از SAT را به نمونه معادلِ آن در ۳SAT کاهش داد (البته در زمانِ یک چندجمله ای). اول از همه شما باید با نظریه کوک لوین یک فرمول ربط دهنده بشکل نرمال بسازید، سپس با وارد کردن متغیرهای جدید به شکافتنِ بند (عبارت بولی با بیش از ۳ جزء) بپردازید. برای مثال بندِ (A ∨ B ∨ C ∨ D) می‌تواند با این عبارت (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D) جایگذین شود، جایی که Z یک متغیر جدید است و فقط در این عبارت استفاده می‌شود. کتابی که، راهنمایی برای نظریه تمامیتِ NP بود، و مسئله‌های جدیدی هنوز پیدا می‌شوند و باید در همان کلاسِ پیچیدگی زمانیِ آن دسته، نوشته شوند. | ## جمع‌بندی | اگرچه بسیاری از نمونه‌های کاربردیِ SAT، می‌توانند توسطِ متدهای ابتکاری حل شوند، و سوالِ اینکه آیا یک الگوریتم قطعی در زمانِ چندجمله‌ای برای SAT (و در نتیجه برای تمامیِ مسئله‌های کاملِ NP) وجود دارد، با وجودِ تلاش مشتاقانه ۱۰ ساله توسطِ نظریه پیچیدگی، منطق دانان ریاضی، و بقیه هنوز یک مسئله معروفِ حل نشده‌است، برای جزئیات بیشتر، مقالهٔ مسئله برابری پی و ان‌پی را بنگرید.