نظریه NP

سلام دوستان :)

امروز میخوام درمورد یکی از چالش ها و حل نشده های دنیای کامپیوتر واستون بگم. ولی قبلش باید یه سری تعاریف رو بدونین. فعلا تعریف نظریه NP رو داشته باشین: نظریه ایی هست که به دسته بندی مسائل از نظر سختیشون میپردازه.

از یک نظر مسائل به دو دسته تقسیم میشن: مسائلی که برای اونها الگوریتم وجود داره و مسائلی که واسشون الگوریتم حل وجود نداره. مجموعه ی کل الگوریتم هایی که تو جهان وجود داره، شماراست. اما مسائل ناشماران:) پس ما کلی مسئله داریم‌که الگوریتم نداریم واسشون. حالا، از یه نظر دیگه مسائل به دو دسته تقسیم میشن: ۱. مسائل تصمیم گیری و ۲. مسائل بهینه سازی.

برای اینکه متوجه بشین یه مثال میزنم. مسئله فروشنده دوره گرد ( یه فروشنده که میخواد از همه ی شهرا دقیقا یک بار عبور کنه و دوباره به شهر شروع برگرده ) رو درنظر بگیرین. حالت تصمیم گیریش اینطوریه: آیا مسیری هست که تو شرط مسئله صدق کنه و طول مسیرش از فلان مقدار بیشتر نشه. حالت بهینه اش این شکلیه: آیا مسیری هست که تو شرط مسئله صدق کنه و طول مسیرش بهینه باشه؟ اینجارو داشته باشین.

هر مسئله که حالت بهینه داره، حالت تصمیم گیری هم داره. ما میتونیم مسائل بهینه سازی رو به مسائل تصمیم گیریشون reduce کنیم. یعنی ورژن ساده ترشو که همون حالت تصمیم گیری هستش رو اگه بتونیم حل کنیم، میگیم خب اون حالت بهینه اشم میشه حل کرد. پس حالت بهینه ی مسائل رو تو کلاس های P , NP , .. میشه بزاریم. این کلاس ها چیان؟

کلاس P : کلاس مسائل تصمیم گیری هست، یعنی مسائلی که برای اونها الگوریتم وجود داره، order الگوریتم چند جمله ایی هست و معنیش این میشه که true یا false بودن مسائل رو میتونیم تو زمان چند جمله ایی بگیم.

کلاس NP : این کلاس میگه اگه یکی از جوابای احتمالی مسئله رو بدی به من، تو زمان چند جمله ایی واست میگم true یا false هستش. مسائلی که تا الان راه حل چند جمله ایی براشون به دست نیومده و اثبات نشده که دارن یا ندارن تو این کلاس هستن. (کلاس جذابیه :))

هر مسئله ایی که P هست، NP هم هست. چون حل مسئله ایی اگه P باشه، حتما تو زمان چندجمله ایی میشه T یا F بودنش رو تشخیص بدیم. این یعنی چی؟ P زیر مجموعه ی NP یه. ولی جذابیت حل نشده ی کل این داستانا اینه که رابطه ی NP با P چطوریه. آیا باهم برابرن؟ آیا مخالف همن؟ آیا مسائلی هستن که NP باشن ولی P نباشن؟ اینو بگم که اگه سوال اول جوابش آره باشه، خیلی اتفاقای عجیب غریبی تو دنیا میفته:))

بعد اینکه نفهمیدن رابطشون چطوره،NP complete به وجود اومد. برای اینکه بفهمین چیه باید بدونین reduction که بالاتر هم‌گفتم چیه. یعنی مسئله ها رو بتونی حالت ساده ترشونو پیدا کنی و اگه بتونی مسئله سخته رو تو یکی از کلاس هایی که گفتم بزاری، اون راحته حتما تو همون کلاسه که سخته هست، هست.

کلاس NP complete : شامل مسئله هایی میشه که اولا NP باشن و دوما اینکه هممممه ی مسائل NP بهشون reduce بشه. خب اینطور که نمیشه:| چجوری بریم همه مسائل NP رو پیدا کنیم و بعدش ببینیم آیا reduce میشن به NP complete ؟ یکی از پروفسورای دانشگاه تورنتو اومد اینکارو کرد البته (آقای کوک). ولی با یه روش خیلی ساده تر و بهتر:)) اومد سخت ترین مسئله ی NP رو پیدا کرد (مسئله ی جذاااب SAT) و بعد از اینکه ثابت کرد NP هستش، گف همه ی مسائل NP به SAT میتونن reduce شن و اگه SAT به هر مسئله ای قابل reduce شدن باشه، اون مسئله NPC هستش.

SAT : مسئله ی صدق پذیری یک عبارت منطقی . یعنی یه حالتی از درستی نادرستی یک عبارت که منجر بشه کل عبارت True بشه.

یه تعریف دیگه هم میشه واسه NPC ارائه داد. اینکه اشتراک NP , NP hard باشه. حالا این NP ی سخت چیه؟ سخت ترین نوع NP . اونقد که اگه فقط یکی از این مسائل رو بتونیم تو زمان چند جمله ایی حل کنیم، همممهه ی مسائل NP رو میشه بهش reduce کرد و حل شدنین تو زمان چندجمله ای.

یه فاجعه ! :)) :مسائلی که NPC و NPH هستن، مسائل تصمیم گیرین. مسائل بهینه سازی NPH اصن خیلی خفنن و تو NPC جا نمیشن.

اگه بخوام از NPC مسائل بزنم : SAT , ورژن تصمیم گیری فروشنده دوره گرد و ....

و همین! خیلی پیچیده بود ظاهرش ولی واقعا زیبا بود و دوست داشتم ذهن شمارم درگیر کنم. امیدوارم خوشتون اومده باشه.