DemoVersion
مقدمه
برخی مسائل در کامپیوتر هستند که تاکنون الگوریتم دقیق چندجمله‌ای برای حل آنان معرفی نشده است. برخلاف مسائلی که راه حل چندجمله‌ای دارند و همگی در کلاس P یا Polynomial قرار می‌گیرند، این مسائل در کلاس NP یا Nondeterministic Polynomial time قرار می‌گیرند. بحث پیرامون این مسائل زیاد هست شاید بپرسید اصلا چه اهمیتی دارند؟ خیلی از مسائل مهم مثل پیشبینی ساختار پروتئین الگوریتم از جنس NP هستند[منبع]. مساله پیشبینی ساختار پروتئین الگوریتم در ساخت دارو و بیوانفورماتیک اهمیت فراوانی دارد. برای دیدن مثال‌ها و توضیحات بیشتر می‌تونید این ویدیو از Youtube رو ببینید. اثباتهای زیادی در زمینه اینکه کلاس P همان کلاس NP هست و نیست از طرف محققین برجسته دنیا انجام شده. تا زمان نوشتن این مطلب ۱۱۶ عدد اثبات در زمینه برابر بودن یا نبودن در این صفحه ثبت شده که قابل توجه است.
در کلاس NP، یک زیرمجموعه به نام NP-Complete که به آن NPC نیز می‌گویند وجود دارد و وقتی می‌گوییم یک مساله مطعلق به کلاس NPC است یعنی تمامی مسائل NP به آن قابل کاهش هستند. یا به عبارت دیگر بین مسائل NP سخت‌ترین مسائل هستند. بقول مولوی که می‌گوید «چونک صد آمد نود هم پیش ماست» این مسائل اگر حل شوند بقیه مسائل هم با توجه به اینکه به این مسائل قابل تبدیل هستند و ساده‌تر هستند، توسط حل شدن اینها حل میشوند. دقت کنید که این یک رابطه یک طرفه است.
برای اثبات NPC بودن یک مساله باید دو مرحله را اثبات کنیم. ابتدا اینکه با داشتن جواب میتوان در زمان چند جمله‌ای درست بودن جواب را بررسی کرد و همچنین باید ثابت کنیم که این مساله حداقل به اندازه یک مساله NPC دیگر سخت است. در نتیجه میتوان آن مساله NPC دیگر را به مساله مورد نظر ما کاهش داد یا reduce کزد. شاید بپرسید پس اولین مساله NPC چطور ثابت شده است که NPC هست، وقتی که هیچ مساله NPC دیگری وجود ندارد؟ اثبات اولین مساله NPC که Circuit satisfiability problem است به شکلی دیگری انجام میشود که توصیه می‌کنم اثباتش رو حتما چک کنید به نوعی اثبات ترکیبی از سخت‌افزار و نرم‌افزار را باهم دارد. بعد از این اثبات میکنند مساله 3SAT نیز به اندازه این مساله سخت است و در ادامه بقیه الگوریتم‌ها از طریق یکدیگر و یا از طریق 3SAT اثبات میشوند.
مساله رنگ آمیزی
کمترین تعداد رنگی که با آن بتوان تمامی راس‌های گراف را رنگ‌آمیزی کرد، طوری که دو راس مجاور همرنگ نباشند چیست؟ مساله رنگ آمیزی در واقع همین سوال است. این مساله به ازای دو رنگ در زمان چند جمله‌ای قابل حل کردن میباشد. در ادامه ثابت میکنیم به ازای سه رنگ و بالاتر از آن NPC میباشد. این مساله یک نوع مساله بهینه‌سازی یا optimization problem است اما برای اثبات نیاز داریم به نوعی این مساله را به یک مساله تصمیم‌گیری یا decision problem تبدیل کنیم که جواب بله یا خیر داشته باشد. نسخه تصمیم‌گیری مساله رنگ آمیزی به این صورت است: با داشتن یک گراف و یک K آیا میتوان این گراق را با K رنگ رنگ آمیزی کرد؟ در ادامه ما ابتدا به ازای K=3 این مساله را اثبات میکنیم و سپس به ازای Kهای بالاتر اثبات میکنیم.
ادامه مطلب