قضیه کوک–لوین

در نظریه پیچیدگی رایانشی، قضیه کوک و لوین، که گاه قضیه کوک نیز خوانده می‌شود، نشان می‌دهد که مسئله صدق‌پذیری دودویی مسئله ای ان‌پی کامل است: الگوریتم نمی‌شناسیم که در زمانی کوتاه مسئله صدق‌پذیری را حل کند. این مسئله نخستین مسئله ای است که ان‌پی کامل بودنش نشان داده شده‌است. می‌توان این مسئله را به بسیاری دیگر از مسئله‌ها کاست و ان‌پی کامل بودنشان را نشان داد. این دسته از مسئله‌ها با نام دسته یا کلاس ان‌پی شناخته می‌شوند. از همین روی قضیهٔ کوک و لوین یکی از مهم‌ترین قضیه‌ها در زمینهٔ پیچیدگی رایانشی است. برآیهٔ (نتیچه‌ی) مهم این قضیه چنین است: اگر الگوریتمی با ییچیدگی زمانی چندجمله‌ای یکی از مسئله‌های دستهٔ ان‌پی کامل حل کند، همهٔ مسئله‌های دیگر را نیز می‌توان با پیچیدگی زمانی چندجمله‌ای حل نمود. این برآیه مسئله ای را به نام برابری پی و ان‌پی پیش می‌کشد که یکی از مهم‌ترین پرسشِ‌های بی‌پاسخ در دانش رایانه است. این نظریه به پاس‌داشت استیون کوک و لنوید لوین نام گذاری شده‌است.

پیشینه

پژوهندگان شوروی و آمریکا هم‌زمان نظریهٔ ان‌پی کامل را در پایان دههٔ ۱۹۶۰ و آغاز دههٔ ۱۹۷۰ پدیدآوردند. در آمریکا در سال ۱۹۷۱، استیون کوک مقالهٔ «پیچیدگی قضیهٔ آوین رویه‌ها» را در کنفرانس «انجمن نظریهٔ رایانش» چاپ کرد. به دنبالِ آن، ریچارد کارپ در سال ۱۹۷۲ مقالهٔ «کاهش میانِ مسئله‌های ترکیبی" را چاپ نمود. او به کمک نظریهٔ کوک فهرستی از ۲۱ مسئله ان‌پی-کامل کارپ را شناسایی کرد و نشان داد که چگونه در زمانی کوتاه می‌توان مسئله صدق‌پذیری دودویی را به این مسئله‌ها کاست. از همین روی، ریچارد کارپ و کوک جایزه تورینگ دریافت کردند. سپس، تیودور پی بیکر، جان گیل و روبرت ام سولووی در سال ۱۹۷۵ نشان دادند که حل مسئله‌های ان‌پی در ماشین سروش نیازمند زمانی نمایی است.

در شوروی در سالِ ۱۹۶۹، ام دختیار نتیجه‌ای همانند نتیجهٔ بیکر، گیل و سولووی را به چاپ رسانید. سپس در سال ۱۹۷۳، مقالهٔ لوین «مسئله همگانی جستجو» به چاپ رسید. گرچه پیش از این مقاله در گفت‌وگوها یاد شده بود و در چند سال پیش برای چاپ فرستاده شده بود. دگرسانیِ رویکردِ لوین با رویکردِ کوک و کارپ در این است که لوین جست‌وجوهایی که راه حل را می‌جویند بررسی می‌کرد ولی کوک و کارپ بودنِ چنین راه‌حل‌هایی را بررسی می‌کردند. لوین ۶ مسئله جستجوی مسئله‌های همگانی (ان‌پی کامل) را شناساند و نشان داد که اگر الگوریتم جست‌وجویی با پیچیدگی زمانی چندجمله‌ای باشد که یکی از این مسئله‌ها را حل کند، می‌توان دیگر مسئله‌ها نیز با پیچیدگی زمانی چندجمله‌ای حل نمود.

تعریف‌ها

یک مسئله تصمیم ان‌پی خوانده می‌شود اگر بتوان آن را به کمک یک الگوریتم غیرقطعی در زمان چندجمله ای حل کرد.

یک نمونه (instance) از مسئله صدق‌پذیری دودویی، یک عبارت منطقی است که شامل تعدادی عملگر و متغیر منطقیست.

این مسئله می‌پرسد که آیا می‌توان متغیرهای عبارتی دودویی را چنان ارزش‌دهی کرد که عبارت ارزش درست بگیرد (که در این صورت عبارت صدق پذیر خوانده می‌شود). تاکنون، هیچ پژوهش‌گری الگوریتمی با زمان چندجمله‌ای برای این مسئله نیافته‌است.

ایده

هر مسئله تصمیمی در NP که داده شد، یک ماشین غیرقطعی بسازید که در زمانِ چندجمله‌ای مسئله را حل کند. سپس برای هر ورودی به آن ماشین، یک عبارت بولی بسازید که بگوید ورودی توسطِ ماشین پذیرفته و به درستی اجرا شده و ماشین پاسخ «بله» داده‌است.

سپس عبارت می‌تواند راضی کننده باشد اگر و فقط اگر راهی برای اجرای صحیح و پاسخ «بله» سیستم وجود داشته باشد، بنابراین قابلیت راضی کردن عبارت ساخته شده معادل این پرسش است که آیا ماشین پاسخ «بله» می‌دهد یا خیر.

آوین (اثبات)

این واقعیت براساس گفته‌های Garey و Johnson می‌باشد. دو راه برای اثبات NP کامل بودن مسئله رضایت دودویی وجود دارد. یکی نشان دادنِ اینکه این مسئله NP است! بعدی نشان دادنِ اینکه هر مسئله NP می‌تواند به یک نمونه از مسئله رضایت دودویی کاهش یابد در یک زمان چندجمله‌ای! رضایت دودویی یک NP است چراکه هر مقدارِ دودوییِ تخصیص یافته به متغیرهای دودویی که ادعای رضایت بخش نمودنِ عبارت را دارند، می‌تواند در زمان چندجمله‌ای توسط یک ماشینِ تورینگِ قطعی، بررسی شوند. گفته شد، قابل بررسیِ در زمانِ چندجمله‌ای با ماشین تورینگ قطعی و حل شدنی در زمان چندجمله ای با ماشین تورینگ قطعی! این دو کاملاً معادل اند و سندِ آن می‌تواند در بسیاری کتب پیدا شود برای مثال Sipser’s Introduction to the Theory of Computation بخش ۷٫۳.

حالا فرض کنید مسئله داده شده می‌تواند توسط ماشین تورینگِ غیرقطعی حل شود

"(M = (Q، Σ، s, F، δ"، جایی که Q مجموعه ای از وضعیت هاست، Σ نماد نوار، s ∈ Q وضعیت شروع، F ⊆ Q مجموعه وضعیت‌های پذیرفته شده، و

"{δ: Q × Σ → Q × Σ × {−۱، +۱" مجموعه ای از تحول هاست.

حالا فرض کنید M، یک نمونه از مسئله را در زمانِ (p(n پذیرش یا رد می‌کند جایی که n اندازه نمونه و p تابع چندجمله‌ای است. برای هر ورودی I، یک عبارت بولی که راضی کننده نیز هست به ان اختصاص می‌دهیم اگر و فقط اگر ماشینِ M، ورودیِ I را بپذیرد. عبارت بولی از متغیرها به صورت زیر استفاده می‌کند:

(q ∈ Q، −p(n) ≤ i ≤ p(n), j ∈ Σ، and ۰ ≤ k ≤ p(n

متغیرها	شرح وظیفه	تعداد
T_ijk	درست خواهد بود اگر نوار سلول i شامل علامت j در گام k ام از محاسبات باشد	O(p(n))
H_ik	درست خواهد بود زمانی که هِدِ خواندن و نوشتنِ M، در گامِ k امِ محاسبات، در نوار سلولِ i قرار دارد.	O(p(n))
Q_qk	درست خواهد بود اگر M در وضعیتِ q باشد در گامِ k امِ محاسبات	((O(p(n

اگر یک محاسبهٔ قابلِ قبول در ورودیِ I برای M وجود داشته باشد، پس B راضی کننده خواهد بود با اختصاص Tijk و Hik و Qik شرحِ وظائفشان به عبارت دیگر، اگر B راضی کننده باشد، پس ورودی I برای M یک محاسبه قابل قبول می‌باشد، که گام‌های مشخص شده توسط اختصاص مقادیر به متغیرها را پیروی می‌کند. O(p(n)) متغیر دودویی وجود دارد که هر کدام در فضای ((O(log p(n قابل رمزگذاری اند.

بنابراین تبدیل؛ قطعاً در زمان چندجمله‌ای رخ می‌دهد چراکه تعداد بندها ((O(p(n می‌باشد و اندازه B برابر می‌باشد با:

O(log(p(n))p(n))

نتیجه

اثبات نشان می‌دهد هر مسئله NP می‌تواند در یک زمانِ چندجمله ای به یک نمونه مسئله رضایت دودویی کاهش یابد (تبدیل شود)

این یعنی، اگر مسئله رضایت بولی بتواند در زمان چندجمله ای توسط ماشینِ تورینگ غیرقطعی حل شود، پس تمامیِ مسئله‌های NP می‌تواند در زمانِ چندجمله ای حل شود و بنابراین کلاس پیچیدگی NP برابر با کلاس پیچیدگی P خواهد بود!

اهمیت تمامیتِ NP در سالِ ۱۹۷۲ بوسیله انتشار یک مقاله توسط Richard Karp روشن شد. «قابلیت کاهش میانِ مسئله‌های ترکیبی» که در آن ۲۱ ترکیبِ گوناگون و مسئله‌های نظریه گراف‌ها را نشان داد.

روشِ کارپ برای اثباتِ کامل بودنِ مسئله‌هایش، بوسیله کاهش یک مسئله دیگر (که قبلاً ثابت شده NP کامل هست) به این مسئله صورت گرفت. برای مثال، برای نشان دادن اینکه ۳SAT (رضایت عبارت بولی ۳ متغیره) یک (رضایت عبارت بولی ۳ متغیره) یک NP کامل است، نشان داد که چگونه می‌توان یک نمونه از SAT را به نمونه معادلِ آن در ۳SAT کاهش داد (البته در زمانِ یک چندجمله ای). اول از همه شما باید با نظریه کوک لوین یک فرمول ربط دهنده بشکل نرمال بسازید، سپس با وارد کردن متغیرهای جدید به شکافتنِ بند (عبارت بولی با بیش از ۳ جزء) بپردازید. برای مثال بندِ (A ∨ B ∨ C ∨ D) می‌تواند با این عبارت (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D) جایگذین شود، جایی که Z یک متغیر جدید است و فقط در این عبارت استفاده می‌شود. بندهای با کمتر از ۳ جزء، می‌توانند Padd شوند. برای مثال A می‌تواند با ('A ∨ X' ∨ Y)∧(A ∨ X' ∨ Y)∧('A ∨ X ∨ Y)∧(A ∨ X ∨ Y) جایگزین شود و (A ∨ B) می‌تواند با ('A ∨ B ∨ X)∧(A ∨ B ∨ X) جایگذین شود.

Garey و Johnson بیشتر از ۳۰۰ مسئله کاملِ NP در کتابشان (Computers and Intractability) نشان دادند. کتابی که، راهنمایی برای نظریه تمامیتِ NP بود، و مسئله‌های جدیدی هنوز پیدا می‌شوند و باید در همان کلاسِ پیچیدگی زمانیِ آن دسته، نوشته شوند.

اگرچه بسیاری از نمونه‌های کاربردیِ SAT، می‌توانند توسطِ متدهای ابتکاری حل شوند، و سوالِ اینکه آیا یک الگوریتم قطعی در زمانِ چندجمله‌ای برای SAT (و در نتیجه برای تمامیِ مسئله‌های کاملِ NP) وجود دارد، با وجودِ تلاش مشتاقانه ۱۰ ساله توسطِ نظریه پیچیدگی، منطق دانان ریاضی، و بقیه هنوز یک مسئله معروفِ حل نشده‌است، برای جزئیات بیشتر، مقالهٔ مسئله برابری پی و ان‌پی را بنگرید.

منابع

↑ Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.
↑ Karp, Richard M. (1972). "Reducibility Among Combinatorial Problems". In Raymond E. Miller and James W. Thatcher (editors) (ed.). Complexity of Computer Computations (PDF). New York: Plenum. pp. 85–103. ISBN 0-306-30707-3. Archived from the original (PDF) on 29 June 2011. Retrieved 30 June 2011.
↑ T. P. Baker (1975). "Relativizations of the P = NP question". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037.
↑ Dekhtiar, M. (1969). "On the impossibility of eliminating exhaustive search in computing a function relative to its graph". Proceedings of the USSR Academy of Sciences. 14: 1146–1148. (روسی)
↑ Levin, Leonid (1973). "Universal search problems (روسی: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (روسی: Проблемы передачи информации, Problemy Peredachi Informatsii). 9 (3): 265–266. (روسی), translated into English by Trakhtenbrot, B. A. (1984). "A survey of Russian approaches to perebor (brute-force searches) algorithms". Annals of the History of Computing. 6 (4): 384–400. doi:10.1109/MAHC.1984.10036.
↑ Garey, Michael R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.

—ترجمه شده از منبع انگلیسی Cook Levin Theorem

[1] Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158.

[Karp-2] Karp, Richard M. (1972). "Reducibility Among Combinatorial Problems". In Raymond E. Miller and James W. Thatcher (editors) (ed.). Complexity of Computer Computations (PDF). New York: Plenum. pp. 85–103. ISBN 0-306-30707-3. Archived from the original (PDF) on 29 June 2011. Retrieved 30 June 2011.

[3] T. P. Baker (1975). "Relativizations of the P = NP question". SIAM Journal on Computing. 4 (4): 431–442. doi:10.1137/0204037.

[4] Dekhtiar, M. (1969). "On the impossibility of eliminating exhaustive search in computing a function relative to its graph". Proceedings of the USSR Academy of Sciences. 14: 1146–1148. (روسی)

[5] Levin, Leonid (1973). "Universal search problems (روسی: Универсальные задачи перебора, Universal'nye perebornye zadachi)". Problems of Information Transmission (روسی: Проблемы передачи информации, Problemy Peredachi Informatsii). 9 (3): 265–266. (روسی), translated into English by Trakhtenbrot, B. A. (1984). "A survey of Russian approaches to perebor (brute-force searches) algorithms". Annals of the History of Computing. 6 (4): 384–400. doi:10.1109/MAHC.1984.10036.

[Garey-6] Garey, Michael R. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.