قضیه کوک لوین

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

در نظریه پیچیدگی محاسباتی، قضیه کوک لوین، که همچنین به عنوان قضیه کوک (Cook) هم شناخته می شود، اظهار می کند که Boolean satisfiability problem، یک مسئله ان‌پی کامل است! منظور اینه که، تمامِ مسائل NP با زمانِ چند جمله ای می توانند توسطِ یک ماشین تورینگ به مسئله Boolean Formula Satisfiable کاهش یابد.

نتیجه ی مهم این قضیه اینه که اگر یک الگوریتم با پیچیدگی زمانی قطعی چند جمله ای برای حلِ رضایت بولی وجود داشته باشد، پس برای تمامیِ مسائلِ NP، یک الگوریتم با این پیچیدگی زمانی وجود دارد. همچنین این امر برای مسائلِ ان‌پی کامل هم صاق است. این پرسش که همچین الگوریتمی وجود دارد یا نه، به این اسم مشهور است P Versus NP Problems یا(مسئله برابری پی و ان‌پی) و بارها به عنوانِ مهمترین پرسشِ بی پاسخ در تئوریِ علوم رایانه مطرح شده است. این نظریه به افتخارِ استفن کوک و Lenoid Levin نامگذاری شد.

همکاری ها[ویرایش]

مفهوم تمامیتِ NP (ان‌پی کامل)، در اواخرِ دهه ۶۰ میلادی و اوایل ۱۹۷۰ به طورِ همزمان توسطِ محققان در آمریکا و شوروی (اتحاد جماهیر شوروی سوسیالیستی) ایجاد شد. در ایالات متحده در سال ۱۹۷۱، استفن کوک مقاله ای با عنوان "پیچیدگی قضیه اثبات رویه ها" [۱] در کنفرانس "جدید ترین یافته های انجمن ماشین آلات در تئوری محاسبات" Symposium on Theory of Computing، منتشر کرد.

به دنبالِ آن، مقاله ی "ریچارد کارپ"، "قابلیت کاهش میانِ مسائلِ ترکیبی" [۲] موجِ توجهِ جدیدی را به مقاله ی Cook ایجاد کرد البته با فراهم کردنِ لیستی از ۲۱ مسئله کاملِ NP به این اسمِ ۲۱ مسئله ان‌پی-کامل کارپ. Cook و Richard M. Karp بخاطرِ کارشان جایزه تورینگ دریافت کردند.

جذابیت تئوری در NP کامل، همچنین توسطِ Theodore P نیز افزوده شد. Baker و John Gill و Robert M. Solovay نشون دادند که حلِ مسائل NP در ماشین های اوراکل نیازمند زمانِ نمایی است.[۳]

در شوروی، در سالِ ۱۹۶۹ توسطِ M.Dekhtiar، نتیجه ای همانند نتیجه ی Baker،Gill و Solovay منتشر شد.[۴] بعداً مقاله ی Levin، "مسئله عمومی جستجو" [۵] در سال ۱۹۷۳ منتشر شد، اگرچه قبلاً در گفتگو ها اشاره به آن شده بود و در چند سال قبل برای انتشار ارائه شده بود.

رویکرد Levin اندکی با رویکردِ Cook و Karp فرق می کرد، او مسائل جستجو هایی را مطرح کرد که به دنبالِ راه حل می گردند بجای اینکه فقط وجودش را تشخیص دهند.

او ۶ مسئله جستجوی NP کامل، یا مسائل عمومی فراهم کرد و بعلاوه متوجه شد که هرکدام یک الگوریتم دارند که مسئله را در زمان بهینه حل می کند.

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

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

بعنوان مثال، مسئله رضایت دودویی یک عبارت بولی است که متغیر های دودویی را با استفاده از عملوند های بولی یا رابط‌های منطقی ترکیب می کند.

عبارتی راضی کننده است (Satisfiable) که مقدارِ "درست" به متغیر هایی که کلِ عبارت را "True" می کنند انتساب یابد.

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

هر مسئله تصمیمی در 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) وجود دارد، با وجودِ تلاش مشتاقانه ۱۰ ساله توسطِ تئوری پیچیدگی، منطق دانان ریاضی، و بقیه هنوز یک مسئله معروفِ حل نشده است،. برای جزئیات بیشتر، مقاله ی مسئله برابری پی و ان‌پی را بنگرید.

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

-- ترجمه شده از منبع انگلیسی 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. 
  2. http://www.claymath.org/millennium/P_vs_NP/pvsnp.pdf
  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. 
  7. 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.