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

در کنار این دسته از مسائل، مسائلی نیز وجود دارد که به آنها NP-complete گفته می شود. برای حل این مسائل هیچ الگوریتمی با پیچیدگی چند جمله ای وجود ندارد.

برای روشن تر شدن مفهوم این کلاس پیچیدگی به بررسی مساله جمع زیر مجموعه ها[2] می پردازیم.  فرض کنید مجموعه ای مانند {-7, -3, -2, 5, 8} شامل تعدادی عدد صحیح به ما داده شده است و هدف این است که زیر مجموعه ای در آن یافت کنیم که جمع مولفه های آن برابر صفر شود. در مورد این مثال جواب مثبت است و زیر مجموعه {-3, -2, 5} به عنوان جواب یافت می شود. به روال پیدا کردن اینکه آیا چنین زیر مجموعه ای که جمع مولفه های صفر داشته باشد وجود دارد یا خیر، مساله جمع زیر مجموعه ها گفته می شود.

با بزرگ شدن طول مجموعه، تعداد زیر مجموعه های آن به صورت نمایی رشد کرده و کار  پیدا کردن جواب را مشکل تر می کند. به شکلی که این مساله NP-Complete محسوب می شود. به هر حال اگر جواب را در دست داشته باشیم (که به آن اعتبار نامه نیز گفته می شود) به راحتی می توان مولفه های آن را جمع کرد و صفر بودن آن را تصدیق نمود. بنابراین اگر جمع زیر مجموعه ارائه شده برابر صفر باشد، آن زیر مجموعه به عنوان اثبات یا شاهدی برای جواب مثبت به حقیقت ارائه شده است. الگوریتمی که صحت صفر بودن جمع زیر مجموعه را تصدیق می کند، تصدیق کننده نام دارد. پس در تعریف خواهیم داشت که یک مساله NP است اگر و فقط اگر برای آن تصدیق کننده ای وجود داشته باشد که جواب را در زمان چند جمله ای تصدیق کند. پرواضح است که مساله جمع زیر مجموعه ها NP است.

نکته ای که باید به آن اشاره شود این است که در مورد تصدیق نشدن جواب در زمان چند جمله ای تضمینی وجود ندارد. در واقع مسائلی که تصدیق نشدن آنها نیز در زمان چند جمله ای صورت می گیرند مسائل co-NP نامیده می شوند.

از مهمترین مسائل کلاس NP می توان به مساله فروشنده دوره گرد[3]، تجریه اعداد صحیح[4] و همریختی گراف ها[5] اشاره کرد.