تفاوت میان نسخه‌های «نظریه پیچیدگی محاسباتی»

جز
بدون خلاصه ویرایش
(اصلاح املا، اصلاح سجاوندی، اصلاح ارقام، اصلاح نویسه، اصلاح فاصلهٔ مجازی، اصلاح نویسه‌های عربی)
جز
== معرفی [[Np کامل]] ==
تا این بخش از مقاله مسائلی معرفی شدند که اگر بتوان روشی برای حل آنها حدس زد، در زمان نزدیک به زمان خطی یا حداقل در زمان چند جمله‌ای برحسب ورودی می‌توانستیم صحت راه‌حل را بررسی کنیم؛ ولی '''NP-Complete'''ها مسائلی هستند که اثبات شده به سرعت قابل حل نیستند.
در تئوری پیچیدگی NP-Completeها دشوارترین مسائل کلاس NP هستند و جزء مسائلی می‌باشند که احتمال حضورشان در کلاس P خیلی کم است. علت این امر این می‌باشد که اگر یک راه‌حل پیدا شود که بتواندیک مسئله NP-Complete را حل کند، می‌توان از آن الگوریتم برای حل کردن سریع همه مسائل NP-Complete استفاده کرد. به خاطر این مسئله و نیز بخاطر اینکه تحقیقات زیادی برای پیدا کردن الگوریتم کارآمدی برای حل کردن اینگونه مسائل با شکست مواجه شده‌اند، وقتی که مسئله‌ای به عنوان NP-Complete معرفی شد، معمولاً اینطور قلمداد می‌شود که این مسئله در زمان [[چندجمله‌ای|Polynomial]] قابل حل شدن نمی‌باشد، یا به بیانی دیگر هیچ الگوریتمی وجود ندارد که این مسئله را در زمان [[چندجمله‌ای|Polynomial]] حل نماید.
کلاس متشکل از مسائل '''NP-Complete''' با نام '''NP-C''' نیز خوانده می‌شود.
 
۵

ویرایش