ان‌پی کامل: تفاوت میان نسخه‌ها
محتوای حذف‌شده محتوای افزوده‌شده
جز ربات: افزودن رده از مقاله همسنگ در ویکی‌انگلیسی |
جز ربات:فاصلهٔ مجازی، "ك" و "ي"، غلط املایی |
||
خط ۱۷:
به منظور تعریف این چنین NP بیایید مسئلهٔ مجموع زیر مجموعه‌ها را در نظر بگیرید . فرض کنید به ما تعدادی عدد صحیح داده شده است مثلا {-7و-3و-2 5و 8و} و ما میخواهیم بدانیم که آیا مجموع اعضای یکی از زیر مجموعه‌های آن صفر می‌شود یا نه؟ در این مثال جواب بله است زیرا اعداد -3,-2,5 می توانند این شرط را بررسی کنند.
هنگامیکه مقدار اعداد صحیح ورودی زیاد شود تعداد [[زیر مجموعه]]ها بصورت توانی افزایش می یابد و در حقیقت
در هر حال توجه شود که اگر به ما یک زیر مجموعه مشخص بدهند ( بعضی اوقات گواه نامیده می‌شود ) ما به راحتی می توانیم بررسی کنیم که آیا مجموع آن صفر است یا خیر . ( تنها با جمع کردن اعضای آن [[زیر مجموعه]] ) و اگر مجموع صفر باشد آن زیر مجموعه یک شاهد برای این است که جواب بله است. الگوریتمی که بررسی می‌کند آیادرزیر مجموعه داده شده مجموع اعضا صفر است بررسی کننده نامیده می شود.
'''یک
چند جمله ای اجرا شود.'''
در مورد
توجه شود که در تعریف بر پایهٔ بررسی کننده NP نیازمند یک بررسی کننده بعنوان گواه برای جواب نه نیست. آن کلاس مسائلی که شامل یک شاهد این چنینی هستند CO-NP نامیده می شود. در حقیقت یک سوال بدون جواب دیگری در اینجا وجود دارد که آیا تمام مسائل NP دارای یک گواه برای جواب نه هستند و در نتیجه CO-NP می شوند.
خط ۳۵:
مثال
در اینجا یک
تمام مسائل P (برای یک گواه مسئله P ما می توانیم کلا گواه را نادیده بگیریم و
مسئله پیدا کردن مقسوم علیه‌های یک عدد صحیح: دو عدد صحیح N و K داده شده اند.می خواهیم بدانیم آیا عدد صحیحی مثل F وجود دارد که 1<F<K و N بر F بخش پذیر باشد.
مسئله یکریختی دو [[گراف]] که یکریخت بودن دو گراف را بررسی می‌کند .
حالت‌های متفاوت
مساله درستی منطقی که در آن می خواهیم بدانیم آیا یک فرمول منطقی در زبان منطق می تواند به ازای مقادیری از متغیرها راست باشد یا خیر.
خط ۵۱:
به این علت که بسیاری مسئلهٔ مهم در این کلاس وجود دارد تلاش‌های فراوانی برای پیدا کردن الگوریتم هایی با زمان اجرای چند جمله ای برای مسائل NP صورت گرفته است. با این وجود باز هم مسائلی از NP باقی می مانند که در برابر این تلاشها مقاومت می کنندو به نظر می رسد که نیازمند زمان اجرای فراتر از چند جمله ای هستند. اینکه آیا این مسائل اصلا قابل بررسی در زمان اجرای چند جمله ای هستند یا خیر از بزرگترین مسائل در علم کامپیوتر است. ( به مسئله P=NP مراجعه شود)
یکی از مفاهیم مهم در این مبحث مجموعه مسائل NP-Complete است که زیر مجموعهٔ NP به شمار می آید و به صورت غیر رسمی تر می تواند بعنوان سخت‌ترین مسائل NP به شمار بیایند. اگر یک [[الگوریتم]] زمان اجرای چند جمله ای حتی برای یکی از این مسائل پیدا شود آنگاه برای تمام این مسائل الگوریتمی با زمان اجرای چند جمله ای پیدا خواهد شد.
بنا بر این علت و همچنین این علت که تا کنون تمامی تحقیقات برای بدست آوردن چنین الگوریتمی برای هر یک از این مسائل به شکست منجر شده است، هنگامیکه ثابت می‌شود
=== رابطه با سایر کلاسها ===
NP شامل تمام مسائل P می‌شود زیرا هر کس می تواند با نادیده گرفتن شواهد حل
NP همچنین در مجموعه EXPTIME موجود است. به این علت که [[الگوریتم]]یکسانی برای آن در زمان اجرای توانی موجود است.
CO-NP شامل آن سری مسائلی است که گواه‌های ساده ای برای نادرست بودن دارند که بعضی اوقات مثال نقض نامیده می شود. برای مثال تست اول بودن یک عدد صحیح در حوزهٔ CO-NP قرار می گیرد زیرا می توان غیر اول بودن یک عدد را به راحتی با پیدا کردن یک عامل آن مشخص کرد . NP و CO-NP در کنار هم در اولین سطح بالای P درسلسله مراتب چند جمله ای‌ها قرار دارند.
| |||