نمایش مبدأ برای مسئله P در مقابل NP

{{لحن}}
{{ویکی‌سازی}}
{{حل نشده|علوم رایانه|اگر چک کردن صحت حل یک مسئله آسان باشد، آیا لزوماً حل آن مسئله نیز آسان است؟}}
[[File:Complexity classes.svg|thumb|250px|نموداری از رده‌های پیچیدگی با فرض <math>P\neq NP</math>. تحت این فرض، وجود مسائلی درون '''NP''' اما خارج از P و NP-کامل توسط قضیه لادنر اثبات شد.<ref name="Ladner75">R. E. Ladner "On the structure of polynomial time reducibility," ''[[Journal of the ACM]]'' 22, pp. 151–171, 1975. Corollary 1.1. [http://portal.acm.org/citation.cfm?id=321877&dl=ACM&coll=&CFID=15151515&CFTOKEN=6184618 ACM site].</ref>]]
{{مسائل هزاره}}
'''[[چندجمله‌ای]] P در مقابل NP''' {{انگلیسی|P versus NP Problem}}، مسئله حل‌نشده مهمی در [[علوم کامپیوتر]] است. این مسئله می‌پرسد که آیا هر مسئله‌ای که صحت جواب‌های آن را بتوان به سرعت ارزیابی نمود، به سرعت هم قابل حل شدن است؟ این مسئله یکی از [[مسائل جایزه هزاره]] بوده که توسط [[مؤسسه ریاضیاتی کلی|مؤسسه ریاضیاتی کِلِی]] انتخاب شده و برای نخستین کسی که به آن پاسخ درست دهد، جایزه یک میلیون دلاری تعیین شده‌است.{{مدرک|date=اکتبر ۲۰۲۳}}

اصطلاح ''به سرعت'' ارزیابی و حل شدن مسائل، که در توصیف این مسئله به کار رفت، در علوم کامپیوتر به معنای این است که [[الگوریتم|الگوریتمی]] برای آن وجود دارد که [[زمان اجرای الگوریتم|زمان اجرای]] آن [[چندجمله‌ای]] است، چنان‌که زمان لازم جهت تکمیل وظیفه بر حسب اندازه ورودی الگوریتم، تابع چندجمله‌ای است (در مقابل مرتبه زمانی نمایی). به کلاس کلی مسائلی که بتوان برایشان الگوریتمی با زمان اجرای چندجمله‌ای ارائه نمود، «کلاس P» یا صرفاً «[[P (پیچیدگی)|P]]» گفته می‌شود. برای برخی مسائل راه شناخته شده‌ای جهت یافتن سریع پاسخ‌ها وجود ندارد، اما می‌توان جواب‌های پیشنهادی را به سرعت ارزیابی کرد. کلاس مسائلی که بتوان پاسخ‌های پیشنهادیشان را ''به سرعت'' ارزیابی کرد را [[NP (پیچیدگی)|NP]] نامیده که مخفف Nondeterministic Polynomical time بوده که ترجمه تحت‌اللفظی آن به صورت «زمان چندجمله‌ای غیرقطعی» (یا زمان اجرای چندجمله‌ای غیرقطعی) است.<ref group="یادداشت‌ها">یک [[ماشین تورینگ غیرقطعی]] قادر است به حالتی منتقل شود که توسط حالت پیشین تعیین نشده‌است. چنین ماشینی می‌تواند یک مسئله '''NP''' را با افتادن شانسی در حالت جواب صحیح، به صورت چندجمله‌ای حل کرده و طبق معمول آن را ارزیابی کند. چنین ماشین‌هایی جهت حل واقع‌گرایانه مسائل عملی نبوده اما می‌توان از آن‌ها به عنوان مدل‌های نظری استفاده نمود.</ref>

جواب به سؤال '''[[P (پیچیدگی)|P]]''' در مقابل '''[[NP (پیچیدگی)|NP]]''' تعیین خواهد کرد که آیا مسائل قابل ارزیابی در زمان چندجمله‌ای را می‌توان در زمان چندجمله‌ای نیز حل نمود یا خیر. اگر مشخص شود که <math>\bf{P}\neq\bf{NP}</math> است (چنان‌که باور عموم نیز بر همین مبناست)، به این معنا خواهد بود که مسائلی در '''NP''' وجود دارند ه محاسبه آن از ارزیابی اش دشوارتر است: یعنی نمی‌توان آن‌ها را در زمان چندجمله‌ای حل کرد، اما جواب‌هایش را می‌توان در زمان چندجمله‌ای حل نمود.

جدا از مهم بودن این مسئله در [[نظریه محاسبه]]، اثبات هر کدام از دو حالت ممکن آن دارای پی‌آمدهای ژرفی در [[ریاضیات]]، [[رمزنگاری]]، [[الگوریتم جست و جو]]، [[هوش مصنوعی]]، [[نظریه بازی‌ها]]، پردازش چندرسانه‌ای، [[فلسفه]]، [[علم اقتصاد|اقتصاد]] و سایر زمینه‌هاست.<ref>{{Cite book|title=The Golden Ticket: P, NP, and the Search for the Impossible|url=https://archive.org/details/goldenticketpnps0000fort|last=Fortnow|first=Lance|publisher=Princeton University Press|year=2013|isbn=978-0-691-15649-1|location=Princeton, NJ}}</ref>

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

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

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

با این تعاریف، مهم‌ترین سؤال این است که رابطه این دو کلاس چگونه است؟ آیا P=NP؟ بیشتر متخصصین علوم کامپیوتر معتقدند که P با NP برابر نیست با وجود این که هنوز قادر به درک چرایی آن یا اثبات آن در قالب تئوری نیستیم.<ref name="Aaronson 2008 pp. 62–69">{{cite journal | last=Aaronson | first=Scott | title=THE LIMITS OF Quantum | journal=Scientific American | publisher=Scientific American, a division of Nature America, Inc. | volume=298 | issue=3 | year=2008 | issn=00368733, 19467087 | jstor=26000518 | pages=62–69 | url=http://www.jstor.org/stable/26000518 | access-date=2023-01-08}}</ref> در یک نظرسنجی در سال ۲۰۰۲ از ۱۰۰ محقق، ۶۱ نفر به این پرسش پاسخ منفی دادند، ۹ نفر پاسخ مثبت و ۲۲ نفر هنوز مطمئن نبودند. ۸ نفر هم معتقد بودند که شاید پرسش خارج از اصول موضوعه پذیرفته شده کنونی باشد؛ بنابراین رد یا اثبات آن غیرممکن است.

== تعریف‌های رسمی برای کلاس‌های P و NP ==
تعریف [[مسئله تصمیم]]‌گیری: مسئله‌ای که یک رشته به عنوان ورودی دریافت کرده و پاسخ ''"بله"'' یا ''"خیر"'' می‌دهد.{{سخ}}
اگر یک الگوریتم وجود داشته باشد (یک [[ماشین تورینگ]] یا یک [[برنامه (رایانه)|برنامه رایانه‌ای]] با حافظه نامتناهی) که قادر باشد به ازای هر ورودی به طول <math>n</math> در حداکثر <math>c \cdot n^k</math> مرحله که <math>k</math> و <math>c</math> اعداد ثابتی مستقل از طول ورودی هستند، پاسخ درست بدهد؛ آن گاه می‌گوییم مسئله می‌تواند در زمان چندجمله‌ای حل شود و آن را در کلاس P قرار می‌دهیم.

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

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

== تعریف NP-complete ==
برای حل این مسائل هیچ الگوریتمی با پیچیدگی چندجمله‌ای وجود ندارد.

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

== جستارهای وابسته ==
* [[نظریه پیچیدگی محاسباتی]]
* [[پیچیدگی زمانی]]
* [[طراحی الگوریتم]]
* [[مهندسی الگوریتم]]
* [[P (پیچیدگی)]]
* [[NP (پیچیدگی)]]
* [[الگوریتم ان‌پی-آسان]]
* [[ان‌پی سخت]]
* [[ان‌پی کامل]]
* [[ان-پی کامل قوی]]

== یادداشت‌ها ==
{{پانویس|گروه=یادداشت‌ها|۲}}

== منابع ==
{{پانویس|چپ‌چین=بله}}
* {{یادکرد-ویکی|پیوند=https://en.wikipedia.org/w/index.php?title=P_versus_NP_problem&oldid=1019662286|عنوان=P versus NP problem|زبان=انگلیسی|بازیابی=۲۵ آوریل ۲۰۲۱}}

== برای مطالعه بیشتر ==
{{چپ‌چین}}
* {{cite book | last = Cormen | first = Thomas | title = Introduction to Algorithms | publisher = [[MIT Press]] | location = Cambridge | year = 2001 | isbn = 978-0-262-03293-3 | title-link = Introduction to Algorithms}}
* {{cite book | last1 = Garey | first1 = Michael | last2 = Johnson | first2 = David | title = Computers and Intractability: A Guide to the Theory of NP-Completeness | url = https://archive.org/details/computersintract0000gare | url-access = registration | publisher = [[W. H. Freeman and Company]] | location = San Francisco | year = 1979 | isbn = 978-0-7167-1045-5}}
* {{cite book | last = Goldreich | first = Oded | title = P, NP, and NP-Completeness | publisher = Cambridge University Press | location = Cambridge | year = 2010 | isbn = 978-0-521-12254-2}} [http://www.wisdom.weizmann.ac.il/~oded/bc-drafts.html Online drafts]
* {{Cite journal | last1 = Immerman | first1 = N. | title = Languages that Capture Complexity Classes | pages = 760–778 | year = 1987 | journal=SIAM Journal on Computing | volume=16 | issue = 4 |doi=10.1137/0216051| citeseerx=10.1.1.75.3035}}
* {{cite book | last = Papadimitriou | first = Christos | title = Computational Complexity | url = https://archive.org/details/computationalcom0000papa | publisher = Addison-Wesley | location = Boston | year = 1994 | isbn = 978-0-201-53082-7}}
{{پایان چپ‌چین}}

== پیوند به بیرون ==
{{چپ‌چین}}
* {{cite web | last1= Fortnow | first1 = L. | last2 = Gasarch | first2 = W. | title = Computational complexity | url = http://weblog.fortnow.com}}
* [https://www2.eecs.berkeley.edu/Pubs/TechRpts/2017/EECS-2017-146.pdf Aviad Rubinstein's ''Hardness of Approximation Between '''P''' and '''NP'''''], winner of the [[انجمن ماشین‌های حسابگر]]'s [https://awards.acm.org/about/2017-doctoral-dissertation 2017 Doctoral Dissertation Award].
* {{cite web |title=P vs. NP and the Computational Complexity Zoo |date=26 August 2014 |url=https://www.youtube.com/watch?v=YX40hbAHx3s |via=[[یوتیوب]]}}
{{پایان چپ‌چین}}

{{کلاس‌های پیچیدگی}}

[[رده:بهینه‌سازی ریاضی]]
[[رده:حدس‌ها]]
[[رده:علوم رایانه در ۱۹۵۶ (میلادی)]]
[[رده:مسئله‌های حل‌نشده در ریاضیات]]
[[رده:مسئله‌های حل‌نشده در علوم رایانه]]
[[رده:مسائل هزاره]]
[[رده:معرفی‌شده‌های مرتبط با رایانه در ۱۹۵۶ (میلادی)]]
[[رده:نظریه پیچیدگی ساختاری]]