باز کردن منو اصلی

مسئله برابری پی و ان‌پی

Euler diagram for P, NP, ان‌پی کامل، and NP-hard set of problems

رابطهٔ میانِ کلاس‌های پیچیدگی "P و NP" یکی از پرسش‌های بی‌پاسخ در علوم رایانه نظری و از مهم‌ترین پرسش‌ها در این زمینه است.

سؤالِ «آیا P=NP؟» در واقع این است که «آیا آسانیِ تحقیقِ درستیِ پاسخِ یک پرسش، آسانیِ پاسخ گفتنِ آن پرسش را به همراه می‌آورد؟». (اگر با سرعت چندجمله‌ای بتوان درستی پاسخ را تأیید کرد آیا می‌شود با سرعت چندجمله‌ای آن را پاسخ گفت؟)

برای نمونه، مسئلهٔ جمع اعضای زیرمجموعه را در نظر بگیرید. این یک مثال از مسئله‌ای است که تحقیق درستی پاسخِ آن ساده است، اما باور بر این است (اما اثبات نشده‌است) که محاسبه جواب آن «مشکل» است. فرض کنید یک مجموعه از اعداد صحیح داده شده‌است، آیا یک زیر مجموعه ناتهی از آن هست که مجموع اعضای آن، صفرشود؟ برای نمونه، آیا مجموعهٔ {۲-، ۳-، ۱۵، ۱۴، ۷، ۱۰-}، زیرمجموعه‌ای دارد که مجموع اعضای آن صفر باشد؟ پاسخ، مثبت است زیرا زیرمجموعهٔ {۲-، ۳-، ۱۵، ۱۰-}، چنین است. تحقیقِ این که این زیرمجموعه، پاسخِ درست است یا خیر تنها با انجام سه عمل جمع، شدنی است. با این حال، پیدا کردن این مجموعه در آغاز کار، کمی وقت گیر است. به اطلاعاتی که برای تحقیق پاسخ مثبت به این دست پرسش‌ها نیاز است، یک "Hajcertificate" گفته می‌شود. با در اختیار داشتن این اطلاعات درست، تحقیق درست بودن پاسخ در مسئله ما، در زمان چندجمله‌ای امکان‌پذیر است. بنابر این، این مثال در کلاس NP قرار می‌گیرد.

پاسخ به پرسش P=NP مشخص خواهد کرد که آیا راه حل مسائلی مانند جمع اعضای زیرمجموعه به سادگی تحقیق درستی پاسخ آن هاست یا خیر. در صورتی که ثابت شود P≠NP، آنگاه می‌توان نتیجه گرفت که بعضی مسائل وجود دارند که به صورت ذاتی، یافتن پاسخ آنها، "سخت تر" از تحقیق درستی پاسخ است.

مؤسسه ریاضیات Clay، جایزه یک میلیون دلاری برای اولین اثبات درست این مسئله تعیین کرده‌است.[۱]

مفهوم مسئلهویرایش

ارتباط بین کلاس‌های پیچیدگی P و NP در نظریه پیچیدگی محاسباتی -بخشی از نظریه محاسبات که به بررسی منابع مورد نیاز در زمان محاسبه جواب یک مسئله می‌پردازد- مطالعه می‌شود. مهم‌ترین منابع یکی زمان (مراحل یا گام‌های مورد نیاز برای دستیابی به جواب) و دیگری فضا (حافظه مورد نیاز برای حل مسئله) است.

در آنالیزهایی شبیه به این، یک مدل از رایانه‌ای که باید بر طبق آن، زمان محاسبه شود مورد نیاز است. به‌طور معمول، این مدل‌ها فرض می‌کنند که رایانه، "قطعی" (به این مفهوم که به ازای یک حالت معین و برای تمامی ورودی‌ها، رایانه تنها می‌تواند یک عمل ممکن انجام دهد) و "ترتیبی" (به این معنی که عملی را بعد از عمل دیگر انجام می‌دهد) است.

در این نظریه، کلاس P شامل تمام مسئله‌های تصمیم‌گیری است -در زیر تعریف شده- که پاسخ به آن‌ها بر روی یک ماشین قطعی ترتیبی، در زمان چندجمله‌ای به ازای ورودی، ممکن باشد؛ کلاس NP شامل تمام مسئله‌های تصمیم‌گیری است که پاسخ‌های مثبت آن‌ها می‌تواند در زمان چندجمله‌ای با اطلاعات درست، تحقیق شود یا به‌طور معادل، پاسخ‌های آن‌ها در زمان چندجمله‌ای بر روی یک ماشین غیر قطعی، یافت شود.[۲]

با این تعاریف، مهم‌ترین سؤال این است که رابطه این دو کلاس چگونه است؟ آیا P=NP؟

در یک نظرسنجی در سال ۲۰۰۲ از ۱۰۰ محقق، ۶۱ نفر به این پرسش پاسخ منفی دادند، ۹ نفر پاسخ مثبت و ۲۲ نفر هنوز مطمئن نبودند. ۸ نفر هم معتقد بودند که شاید سؤال خارج از اصول موضوعه پذیرفته شده کنونی باشد بنابراین رد یا اثبات آن غیرممکن است.[۳]

تعریف‌های رسمی برای کلاس‌های P و NPویرایش

تعریف مسئله تصمیم‌گیری: مسئله‌ای که یک رشته به عنوان ورودی دریافت کرده و پاسخ "بله" یا "خیر" می‌دهد.
اگر یک الگوریتم وجود داشته باشد (یک ماشین تورینگ یا یک برنامه رایانه‌ای با حافظه نامتناهی) که قادر باشد به ازای هر ورودی به طول   در حداکثر   مرحله که   و   اعداد ثابتی مستقل از طول ورودی هستند، جواب درست بدهد آنگاه می‌گوییم مسئله می‌تواند در زمان چندجمله‌ای حل شود و آن را در کلاس P قرار می‌دهیم.

NP-کاملویرایش

یک پیشرفت مهم در مسئلهٔ «برابری P و NP» در اوایل دههٔ ۷۰ میلادی توسط استفان کوک و لئونید لوین رخ داد. آن‌ها چند مسئله در NP کشف کردند که پیچیدگی آن‌ها به تنهایی به پیچیدگی کل کلاس مربوط است. اگر یک الگوریتم چندجمله‌ای برای هر یک از این مسائل وجود داشته باشد، همهٔ مسائل NP در زمان چندجمله‌ای قابل حل خواهند بود. این مسائل NP-کامل نام دارند. پدیدهٔ تمامیت NP، هم به دلایل نظری و هم عملی دارای اهمیت است.

از جنبهٔ نظری محققی که سعی می‌کند نشان دهد P برابر NP نیست، ممکن است روی یک مسئلهٔ NP-کامل تمرکز کند. اگر هر مسئله در NP بیشتر از زمان چندجمله‌ای نیاز داشته باشد، مسئلهٔ NP-کامل نیز چنین خواهد بود. به علاوه محققی که تساوی P و NP را بررسی می‌کند، کافی‌ست یک الگوریتم چند جمله‌ای برای یک مسئلهٔ NP-کامل پیدا کند تا به این هدف برسد.

تعریف NP-completeویرایش

برای حل این مسائل هیچ الگوریتمی با پیچیدگی چندجمله‌ای وجود ندارد.

آیا P به معنی سادگی است؟!ویرایش

بله

چرا بسیاری از محققین فکر می‌کنند P≠NP؟ویرایش

پی آمدهای اثباتویرایش

نتایج در مورد سختی اثباتویرایش

الگوریتم‌های زمان-چندجمله‌ایویرایش

توصیفات منطقیویرایش

توصیفات منطقی وجود ندارد

منابعویرایش

  • ویکی‌پدیای انگلیسی:
  1. Millennium Prize problems, 2000-05-24 Retrieved on 2008-01-12.
  2. Sipser, Michael: Introduction to the Theory of Computation, Second Edition, International Edition, page 270. Thomson Course Technology, 2006. Definition 7.19 and Theorem 7.20.
  3. William I. Gasarch (June ‎2002), "The P=?NP poll.", SIGACT News, 33 (2), p. 34–47, ISSN doi: [http://dx.doi.org/%7B%7Burlencode:10.1145/1052796.1052804 [[Digital object identifier|doi]]: <span class="neverexpand"> [http://dx.doi.org/%7B%7Burlencode:10.1145/1052796.1052804 Check |issn= value (help) Check date values in: |تاریخ= (help) 10.1145/1052796.1052804] Retrieved on 2008-12-29.