قبلا این جا و این جا توضیح داده بودم .
کلاس p : به مسائل انتخاب (decission problem ) که الگوریتمی با پیچیدگی زمانی چند جمله ای ( polynomial ) براشون موجود باشه مسائل کلاس p میگیم .
مثال ۱ : مسائلی مثل آیا گراف دور همیلتونی دارد ؟
مثال ۲: آیا با داشتن یک جمله و یک گرامر آیا جمله قابل ساختن بوسیله گرامر مورد نظر هست ؟ ( میتونید این مسائل رو داخل این لینک ببینید )
نکته ۱ : منظور از decission problem یعنی مسئله ۲ حالت داره یا درست یا غلط .مثلا این سوال که آیا عدد ورودی زوج است یا نه ؟
نکته ۲ : منظور از چند جمله ای عبارتی به شکل روبرو هستش .
که میشه با استفاده از سری به این شکل هم نمایش داد :
د 
پس طبیعتا عباراتی مثل n^n یا n! جزو چند جمله ای ها حساب نمیشن .
کلاس Np (مخفف nondetermenestic polynomial ) : به مسائل انتخابی (decission problem ) که با داشتن یک جواب میشه درستی یا نادرستی جواب رو با استفاده از یک الگوریتم با پیچیدگی زمانی چند جمله ای تعیین کرد مسائل کلاس NP گفته میشه .
مثال:
فرض کنید یک مجموعه شامل ۴۰۰ عضو دارید , یک رابطه بین هر ۲ نفر وجود داره این که آیا این ۲ نفر با هم سازگار هستند یا نه ؟
خب حالا فرض کنید می خواهید بدونید که آیا یک مجموعه ۱۰۰ عضوی که هر ۲ نفر داخلش با هم سازگار باشن وجود داره با نه .
این مسئله NP حساب میشه چون با دادن یک جواب میشه درستی یا نادرستیشو در محدوده زمانی چند جمله ای مشخص کرد .یعنی مثلا اگر اسم ۱۰۰ نفر داده بشه میشه مشخص کرد که آیا این ۱۰۰ نفر با هم سازگار هستند یا نه .
ولی چزو کلاس P نیست چون پیچیدگی زمانی این مسئله مشخص نیست که چند جمله ای هست یا نه . به این دلیل که یک الگوریتم میتونه این باشه که تمام حالت های انتخاب 100 از ۴۰۰ رو بررسی کنیم و ببینیم آیا مجموعه مورد نظر ما موجوده یا نه ولی خب همین جور که میدونید انتخاب ۱۰۰ از ۴۰۰ خیلی خیلی بزرگه(در حد تمام اتم های دتیا ) و قابل انجام نیست و در حالت کلی تر که مجموعه n تا عضو داشته باشه پیچیدگی زمانی این الگوریتم n^n میشه که چند جمله ای حساب نمیشه . البته هنوز نمیدونیم که آیا با الگوریتم های بهتر میشه به پیچیدگی زمانی چند جمله ای رسید یا نه ؟
آیا کلاس p زیر مجموعه کلاس NP هست ؟
بله هر مسئله کلاس P زیر مجموعه کلاس NP هست چون مسئله P خودش با پیچیدگی زمانی چند جمله ای قابل حله پس در صورت داشتن جواب میشه درستی یا نادرستشو تعیین کرد ( یعنی همون ویژگی کلاس NP ) پس جزو کلاس NP هم هست .
آیا کلاس Np زیر مجموعه کلاس P هست ؟
این سوال رو به این شکل میشه مطرج کرد که آیا میشه برای هر سوال NP الگوریتمی از پیچیدگی زمانی چند جمله ای پیدا کرد ؟
در صورت مشخص شدن جواب این سوال میشه تعیین کرد که ایا P=NP هست یا نه . ولی هنوز کسی جواب این سوال رو نمی دونه. جالبه که بدونین این یکی از مسائل ریاضی حل نشده توی دنیا هست که ۱ میلیون دلار جایزه هم داره .
Np-Hard : مسئله ای هستنش که در صورت پیدا شدن الگوریتم از درجه چند جمله ای میشه تمام مسائل NP رو به این مسئله تبدیل کرد و با پیچیدگی چند جمله ای حل کرد.
.
به روشی که مسائل Np به NP_Hard تبدیل میشن Reduction میگیم .
منظور از Reduction اینه که فرض کنید که یک مسئله داریم که یکسری ورودی خاص داره مثلا X و یک مسئله دیگه داریم با ورودی Y حالا اگر بشه X رو بشکلی با درجه چند جمله ای به Y تبدیل کرد اصطلاجا Reduction بهش گفته میشه .
یعنی بطور خلاصه Reduction یعنی تبدیل ورودی یک مسئله به یک مسئله دیگه .
به الگوریتم از درجه چند جمله ای 
(C یک ثابت هستش) . که برای Reduction ( یا تبدیل ورودی ۲ مسئله به هم) استفاده میشه polynomial-time reduction algorithm. میگن .
NP_Complete : مسائلی که هم Np هستند و هم NP_Hard . یعنی هم باید در صورت دادن یک جواب بشه درستی جواب رو در مدت زمان چند جمله ای بررسی کرد و هم بشه بقیه مسائل NP رو به این مسئله کاهش داد .
مثل Knapscak یا پیدا کردن دور همیلتونی در گراف یا traveling-salesman و...
ضمنا تمام مسائل Np-complete با استفاده از Reduction قابل تبدیل به هم هستند .