![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Complexity_classes.svg/langfa-640px-Complexity_classes.svg.png&w=640&q=50)
مسئله P در مقابل NP
From Wikipedia, the free encyclopedia
چندجملهای P در مقابل NP (به انگلیسی: P versus NP Problem)، مسئله حلنشده مهمی در علوم کامپیوتر است. این مسئله میپرسد که آیا هر مسئلهای که صحت جوابهای آن را بتوان به سرعت ارزیابی نمود، به سرعت هم قابل حل شدن است؟ این مسئله یکی از مسائل جایزه هزاره بوده که توسط مؤسسه ریاضیاتی کِلِی انتخاب شده و برای نخستین کسی که به آن پاسخ درست دهد، جایزه یک میلیون دلاری تعیین شدهاست.[نیازمند منبع]
![]() | لحن یا سبک این مقاله بازتابدهندهٔ لحن دانشنامهای مورد استفاده در ویکیپدیا نیست. |
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |
اگر چک کردن صحت حل یک مسئله آسان باشد، آیا لزوماً حل آن مسئله نیز آسان است؟
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Complexity_classes.svg/320px-Complexity_classes.svg.png)
اصطلاح به سرعت ارزیابی و حل شدن مسائل، که در توصیف این مسئله به کار رفت، در علوم کامپیوتر به معنای این است که الگوریتمی برای آن وجود دارد که زمان اجرای آن چندجملهای است، چنانکه زمان لازم جهت تکمیل وظیفه بر حسب اندازه ورودی الگوریتم، تابع چندجملهای است (در مقابل مرتبه زمانی نمایی). به کلاس کلی مسائلی که بتوان برایشان الگوریتمی با زمان اجرای چندجملهای ارائه نمود، «کلاس P» یا صرفاً «P» گفته میشود. برای برخی مسائل راه شناخته شدهای جهت یافتن سریع پاسخها وجود ندارد، اما میتوان جوابهای پیشنهادی را به سرعت ارزیابی کرد. کلاس مسائلی که بتوان پاسخهای پیشنهادیشان را به سرعت ارزیابی کرد را NP نامیده که مخفف Nondeterministic Polynomical time بوده که ترجمه تحتاللفظی آن به صورت «زمان چندجملهای غیرقطعی» (یا زمان اجرای چندجملهای غیرقطعی) است.[یادداشتها 1]
جواب به سؤال P در مقابل NP تعیین خواهد کرد که آیا مسائل قابل ارزیابی در زمان چندجملهای را میتوان در زمان چندجملهای نیز حل نمود یا خیر. اگر مشخص شود که است (چنانکه باور عموم نیز بر همین مبناست)، به این معنا خواهد بود که مسائلی در NP وجود دارند ه محاسبه آن از ارزیابی اش دشوارتر است: یعنی نمیتوان آنها را در زمان چندجملهای حل کرد، اما جوابهایش را میتوان در زمان چندجملهای حل نمود.
جدا از مهم بودن این مسئله در نظریه محاسبه، اثبات هر کدام از دو حالت ممکن آن دارای پیآمدهای ژرفی در ریاضیات، رمزنگاری، الگوریتم جست و جو، هوش مصنوعی، نظریه بازیها، پردازش چندرسانهای، فلسفه، اقتصاد و سایر زمینههاست.[2]