NP چیست؟

[1]NP یکی از ساده ترین کلاس های پیچیدگی در تئوری پیچیدگی در نظریه زبان محسوب می شود.  اساسا NP شامل تمام مسائل تصمیم گیری می شود، که در آنها خروجی مثبت به معنی اثبات شدن درستی یک حقیقت است. به طور دقیق تر، این اثبات ها باید در زمان چند جمله ای با استفاده از یک ماشین قطعی تورینگ قابل تصدیق شدن باشند. در تعریفی مشابه گفته می شود که NP مجموعه ی مسائل تصمیم گیری است که در زمان چند جمله ای و با استفاده از ماشین غیر قطعی تورینگ قابل حل شدن هستند.