در نظریه پیچیدگی محاسباتی NPیکی از بنیادی ترین کلاس ها است. NP مخفف عبارت «Non-Deterministic Polynomial» است که به زمان اجرای آن اشاره دارد.NP مجموعهٔ کلیه مسائل تصمیم گیری است که پیدا کردن جواب بله برای آن ها شامل اثبات ساده ای است که جواب حقیقتاً باید بله باشد. به طور دقیق تر این اثبات های ساده باید قابل بررسی در یک زمان اجرای چندجمله ای در یک ماشین تورینگ قطعی باشد. در مقابل این تعریف NP مجموعه...
