ان پی کامل

در نظریه پیچیدگی محاسباتی NPیکی از بنیادی ترین کلاس ها است. NP مخفف عبارت «Non-Deterministic Polynomial» است که به زمان اجرای آن اشاره دارد.NP مجموعهٔ کلیه مسائل تصمیم گیری است که پیدا کردن جواب بله برای آن ها شامل اثبات ساده ای است که جواب حقیقتاً باید بله باشد. به طور دقیق تر این اثبات های ساده باید قابل بررسی در یک زمان اجرای چندجمله ای در یک ماشین تورینگ قطعی باشد. در مقابل این تعریف NP مجموعه مسائل تصمیم گیری نامیده می شود که در یک زمان اجرای چندجمله ای در یک ماشین تورینگ غیرقطعی قابل بررسی باشند. کلاس پیچیدگی P یکی از اعضای NP است اما NP شامل کلاس های مهم دیگری نیز هست؛ که پیچیده ترین آن ها NP-Complete است به طوری که برای آن ها هیچ الگوریتم شناخته شده قابل اجرا در زمان چندجمله ای وجود ندارد .مهمترین سؤالی که اکنون برای این کلاس ها در این نظریه وجود دارد این است که آیا P=NP؟ این سؤال می پرسد که آیا چنین الگوریتمی واقعاً برای مسائل NP-Complete و در کل NP وجود دارد یا خیر. این باور گسترده وجود دارد که این تساوی نمی تواند درست باشد.
NP را می توان به وسیلهٔ NTIME نیز تعریف کرد:
(NP=∪NTIME(n^kمقدمهویرایشبسیاری از مسئله های معمول علوم کامپیوتر در حوزهٔ مسائل NP قرار دارند. مخصوصاً مدل تصمیم گیری بسیاری از مسائل جستجو و بهینه سازی در حوزهٔ NP قرار دارد.نمونه هایی از زمینه هایی که شامل مسائل NP می شوند عبارتند از:مانند جبر بولی، گراف، طراحی شبکه، زیست شناسی، فیزیک جدید، نظریه اعداد، نظریه بازی ها و پازل ها، نظریه زبان ها و ماشین ها و .. .
به منظور تعریف این چنین NP بیایید مسئلهٔ مجموع زیر مجموعه ها را در نظر بگیرید. فرض کنید به ما تعدادی عدد صحیح داده شده است مثلاً {-۷و-۳و-۲ ۵و ۸و} و ما می خواهیم بدانیم که آیا مجموع اعضای یکی از زیر مجموعه های آن صفر می شود یا نه؟ در این مثال جواب بله است زیرا اعداد -۳، ۵ و -۲ می توانند این شرط را بررسی کنند.