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

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