قضیه کوک لوین

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

پیشینه[ویرایش]

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

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

تعریف‌ها[ویرایش]

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

ایده[ویرایش]

هر مسئله تصمیمی در 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

متغیرها شرح وظیفه تعداد
Tijk درست خواهد بود اگر نوار سلول i شامل علامت j در گام k ام از محاسبات باشد O(p(n))2
Hik درست خواهد بود زمانی که هِدِ خواندن و نوشتنِ M، در گامِ k امِ محاسبات، در نوار سلولِ i قرار دارد. O(p(n))2
Qqk درست خواهد بود اگر 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 ∨ A ∨ A) جایگذین شود و (A ∨ B) می تواند با (A ∨ B ∨ B) جایگذین شود.

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

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

منبع‌ها[ویرایش]

  1. Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. 
  2. ۲٫۰ ۲٫۱ Karp, Richard M. (1972). "Reducibility Among Combinatorial Problems". In Raymond E. Miller and James W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. pp. 85–103. ISBN 0306307073. 
  3. T. P. Baker; J. Gill, R. Solovay (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. 
  6. ۶٫۰ ۶٫۱ Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0716710455. 

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