کلاس 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 هست یا نه . ولی هنوز کسی جواب این سوال رو نمی دونه. جالبه که بدونین این یکی از مسائل ریاضی حل نشده توی دنیا هست که ۱ میلیون دلار جایزه هم داره .