1- بحث در مورد NP-Hard و NP-Complete

Question

در این تاپیک قصد داریم در مورد کلاس های p و np ؛ مفهوم Reduction و مسائلی که می توان آنها را کاهش داد و مسائلی که زیر مجموعه ی این کلاس ها هستند  بحث و تبادل نظر کنیم . در اولین تاپیک در مورد تعریف کلاس p و np و تفاوت آنها بحث می شود.

 

برای شروع :

فرق کلاس های p و np در چیست؟ آیا می توان گفت p زیر مجموعه ی سره np هست ؟

Answer 1

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

 

Comments

پس p زیر مجموعه سره np هست .

 

خب ، موقعی که به مسئله ای مواجه میشیم چطوری باید عضویت اش رو در این دو کلاس جواب بدیم .

در مثال شما تمام حالات رو درنظر گرفتید و حتما به جواب می رسیم اما ممکنه در بدترین حالت با یک تابع هیوریستیک یا تقریبی با زمان چند جمله ای به جواب برسیم

به صورت خلاصه آیا می توان گفت مسئله ی پیشه رو(هر مسئله ) به صورت حتم عضو p یا np است یا باید منتظر ماند ؟

---

با استفاده از تعریف  .اگر مسئله  انتخاب باشه و الگوریتم از مرتبه چند جمله ای براش موجود باشه (1,n , n^2 , .... )  میشه P .
اگر الگوریتم موجود نباشه ولی بشه درستی یکی از جواب ها رو تعیین کرد میشه NP .

---

"؛ اما ممکنه در بدترین حالت با یک تابع هیوریستیک یا تقریبی با زمان چند جمله ای به جواب برسیم ؛" نه در بدترین حالت جواب به شکل فاکتوریل میشه که حد بالاش n^n میشه یعنی اوی بزرگ n^n  و چون n^n چند جمله ای نیست پس اون مسئله  جزو کلاس P نیست (مگر این که الگوریتم بهتری پیدا بشه ) . ولی چون میشه در صورت گرفتن یک مجموعه ۱۰۰ عضوی از ورودی درستی یا نادرستیشو در مدتزمان چند جمله ای محاسبه کرد پس جزو کلاس NP هست .

---

مشکلم در همینه ، وقتی به شما یک مسئله ای رو می دهند از کجا تشخیص می دید که این مسئله عضو p یا np ؟
آیا به صرف اینکه به ذهنمون الگوریتمی با زمان چند جمله ای نمی رسه عضو np میشه ؟
آیا روش formal برای عضویت مسئله ها داریم ؟

---

بعضی وقت ها میشه بعضی از سوالات رو تبدیل کرد به مسائل معروف تر که الگوریتمی براشون پیدا نشده و تشخیص داد . وگرنه من راه formal ای تا حالا ندیدم . فکر کنم اگر راه formal ای پیدا بشه اون مسئله ۱ میلیون دلاری هم حل بشه

Answer 2

در مورد این موضوع یک سری مطلب فهمیدم گفتم اضافه کردن این مطالب به روند کامل شدن این تاپیک شاید کمک بکنه (هرچند  پاسخ BlueBlade تقریبا کامل بود )

 

ما دراین تاپیک به دنبال پیچیدگی زمانی الگوریتم ها هستیم که به آن نظریه پیچیدگی محاسباتی نیز گویند . مسائل موجود ما به دو دسته ی حل پذیر و حل ناپذیر تقسیم می شوند .به

طور کلی 4 کلاس مختلف در این نظریه داریم :P-Np-Np Complete - Np Hard

کلاس مسائل P (Polynomial Time) : مسائلی که عضو این کلاس هستند توسط یک ماشین تورینگ قطعی پذیرفته می شوند و بنابراین ما الگوریتمی در زمان چند جمله ای

برای این مسائل داریم .

کلاس مسائل Np(Non deterministic polynomial Time) : این  کلاس مسائل تصمیم پذیری را در زمان چند جمله ای بررسی می کند که آیا این جواب متعلق به جواب

مسئله هست یا خیر؛ به عبارتی دیگر مسائلی که توسط یک ماشین تورینگ غیر قطعی پذیرفته می شود. مثلا یافتن دور همیلتونی بر اساس یک الگوریتم چند جمله ای نداریم اما می

توان با داشتن یک دور بررسی کرد که آیا این دور همیلتونی هست یا خیر .

مسائل را می توان یک طور دیگه هم دید : 1-حل کردنی :مسئله را با یک الگوریتم حل می کنیم      2- تصدیق کردنی :آیا حل این مسئله جواب مسئله ما هست یا خیر ( مانند مسائل

تصمیم گیری )