ان پی کامل

در نظریه پیچیدگی محاسباتی 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 بیایید مسئلهٔ مجموع زیر مجموعه ها را در نظر بگیرید. فرض کنید به ما تعدادی عدد صحیح داده شده است مثلاً { - ۷و - ۳و - ۲ ۵و ۸و} و ما می خواهیم بدانیم که آیا مجموع اعضای یکی از زیر مجموعه های آن صفر می شود یا نه؟ در این مثال جواب بله است زیرا اعداد −۳، ۵ و −۲ می توانند این شرط را بررسی کنند.
هنگامیکه مقدار اعداد صحیح ورودی زیاد شود تعداد زیر مجموعه ها به صورت توانی افزایش می یابد و در حقیقت مسئله فوق یک مسئله NP - Complete است.
در هر حال توجه شود که اگر به ما یک زیر مجموعه مشخص بدهند ( بعضی اوقات گواه نامیده می شود ) ما به راحتی می توانیم بررسی کنیم که آیا مجموع آن صفر است یا خیر. ( تنها با جمع کردن اعضای آن زیر مجموعه ) و اگر مجموع صفر باشد آن زیر مجموعه یک شاهد برای این است که جواب بله است. الگوریتمی که بررسی می کند آیادرزیر مجموعه داده شده مجموع اعضا صفر است بررسی کننده نامیده می شود.