تستهای NP-کامل معمولاً اثبات نمیخواهند؛ طبقهبندی میخواهند. «این مسئله در P است یا NP-کامل؟»، «کدام کاهش درست است؟»، «اگر فلان مسئله در P باشد، چه نتیجهای میگیریم؟». اگر چهار تعریف را دقیق بدانی، جهت کاهش را درست بگیری و چند مسئلهٔ دوقلو را بشناسی، بیشتر این تستها سریع حل میشوند.
چهار دسته در یک جدول
| دسته | تعریف | نمونه |
|---|---|---|
| P | در زمان چندجملهای حل میشود | کوتاهترین مسیر، ۲-SAT، تطابق |
| NP | هر جواب «بله» را در زمان چندجملهای میشود بررسی کرد | همهٔ مسئلههای P، بهعلاوهٔ SAT و خوشه |
| NP-سخت | هر مسئلهٔ NP به آن کاهش چندجملهای دارد | SAT، و حتی مسئلهٔ توقف |
| NP-کامل | هم در NP است و هم NP-سخت | SAT، ۳-SAT، خوشه، پوشش رأسی |
دو نکته از همین جدول: اول، P زیرمجموعهٔ NP است؛ مسئلهای که حلش آسان است، بررسی جوابش هم آسان است. دوم، NP-سخت لزوماً در NP نیست. مسئلهٔ توقف NP-سخت است ولی اصلاً تصمیمپذیر نیست، چه برسد به اینکه در NP باشد.
یک اشتباه رایج این است که NP را «غیرچندجملهای» بخوانی. NP یعنی «چندجملهای غیرقطعی»: ماشینی که بتواند جواب را حدس بزند، در زمان چندجملهای بررسیاش میکند.
کاهش: جهتش همهچیز است
A ≤p B یعنی هر نمونه از A را میشود در زمان چندجملهای به نمونهای از B تبدیل کرد، طوری که جوابها یکی بمانند. پس B دستکم به سختی A است. برای اثبات NP-سخت بودن مسئلهٔ تازهٔ B، یک مسئلهٔ NP-کامل شناختهشده مثل A را به B کاهش میدهی. اگر برعکس، B را به A کاهش بدهی، فقط ثابت کردهای B از A سختتر نیست.
دو نتیجه که تستها زیاد میپرسند: اگر یک مسئلهٔ NP-کامل در P باشد، آنوقت P = NP. و اگر A ≤p B و B در P باشد، A هم در P است.
زنجیرهٔ کاهشهای مشهور
قضیهٔ کوک–لوین ثابت میکند SAT، یعنی ارضاپذیری فرمول بولی، NP-کامل است. بقیهٔ مسئلههای مشهور با یک زنجیره از آن به دست میآیند:
| کاهش | ایدهٔ اصلی در یک جمله |
|---|---|
| SAT → ۳-SAT | هر بند بلند را با متغیرهای کمکی به چند بند سهلیترالی میشکنی |
| ۳-SAT → خوشه | برای هر لیترال هر بند یک رأس؛ رأسهای بندهای مختلف را که با هم تناقض ندارند وصل میکنی؛ k بند ارضاپذیرند اگر و فقط اگر خوشهٔ k تایی باشد |
| خوشه → مجموعهٔ مستقل | خوشه در G همان مجموعهٔ مستقل در گراف مکمل است |
| مجموعهٔ مستقل → پوشش رأسی | S مستقل است اگر و فقط اگر بقیهٔ رأسها پوشش رأسی باشند |
| پوشش رأسی → دور همیلتونی | برای هر یال یک ابزارک میسازی که دور فقط وقتی از آن میگذرد که یکی از دو سر یال انتخاب شده باشد |
| دور همیلتونی → فروشندهٔ دورهگرد | یالهای گراف وزن ۱ و بقیه وزن ۲ میگیرند؛ دور همیلتونی هست اگر و فقط اگر توری با هزینهٔ n باشد |
| ۳-SAT → جمع زیرمجموعه | هر متغیر و هر بند یک رقم در یک عدد بزرگ میشود |
| ۳-SAT → ۳-رنگآمیزی | ابزارکهایی که رنگآمیزی مجاز را به مقداردهی درست تبدیل میکنند |
دو پیوند این زنجیره را روی ۳۰۰ گراف تصادفی با جستوجوی کامل امتحان کردیم: هر مجموعهٔ مستقل در G دقیقاً یک خوشه در مکمل G است و مکملش یک پوشش رأسی است. یک نتیجهٔ مفید هم دارد که همیشه برقرار بود: اندازهٔ بزرگترین مجموعهٔ مستقل بهعلاوهٔ اندازهٔ کوچکترین پوشش رأسی برابر تعداد رأسهاست.
مسئلههای دوقلو: یکی آسان، یکی سخت
رایجترین اشتباه در تستها قاطی کردن دو مسئلهٔ شبیه است. این جدول را حفظ نکن، دلیلش را بفهم:
| در P | NP-کامل یا NP-سخت | فرق کلیدی |
|---|---|---|
| ۲-SAT | ۳-SAT | بندهای دوتایی را میشود به گراف استلزام تبدیل کرد و با مؤلفههای قویاً همبند حل کرد |
| ۲-رنگآمیزی | ۳-رنگآمیزی | ۲-رنگآمیزی یعنی دوبخشی بودن که با یک جستوجوی BFS بررسی میشود |
| کوتاهترین مسیر | بلندترین مسیر ساده | بلندترین مسیر ساده دور همیلتونی را در خودش دارد |
| دور اویلری | دور همیلتونی | اویلری فقط به درجهٔ رأسها و همبندی بستگی دارد |
| برش کمینه | برش بیشینه | برش کمینه با شار بیشینه حل میشود |
| تطابق بیشینه | تطابق سهبعدی | تطابق در گرافها الگوریتم چندجملهای دارد، سهبعدی نه |
الگوریتم ۲-SAT را با گراف استلزام پیاده کردیم و روی ۲٬۰۰۰ فرمول تصادفی با امتحان همهٔ مقداردهیها مقایسه کردیم؛ همیشه یک جواب داد.
اشتباههای رایج
اشتباه ۱: کولهپشتی با برنامهریزی پویا «چندجملهای» است
الگوریتم برنامهریزی پویای کولهپشتی O(nW) است که W ظرفیت کوله است. این چندجملهای به نظر میرسد ولی نیست: اندازهٔ ورودی تعداد بیتهای W است، یعنی حدود log W، و nW نسبت به log W نمایی است. به این زمان «شبهچندجملهای» میگویند و کولهپشتی هنوز NP-کامل است.
اشتباه ۲: جهت کاهش را برعکس گرفتن
اگر تست بگوید «B را به SAT کاهش دادیم، پس B سخت است»، غلط است. کاهش B به SAT فقط میگوید B در NP یا سادهتر است. برای سختی B باید SAT یا یک مسئلهٔ NP-کامل دیگر را به B کاهش بدهی.
اشتباه ۳: نسخهٔ خاص را با نسخهٔ کلی یکی گرفتن
مسئلهای که در حالت کلی NP-کامل است، ممکن است در حالت خاص آسان باشد. پوشش رأسی در درختها و مجموعهٔ مستقل در گرافهای دوبخشی چندجملهایاند و خوشهٔ k تایی برای k ثابت هم در زمان O(nᵏ) حل میشود. قبل از جواب دادن، ببین مسئله کلی است یا روی ورودی خاص.
پرسشهای پرتکرار
فرق NP-سخت و NP-کامل چیست؟
NP-کامل یعنی هم NP-سخت و هم عضو NP. NP-سخت فقط میگوید دستکم به سختی هر مسئلهٔ NP است و ممکن است خودش در NP نباشد؛ مثل مسئلهٔ توقف یا نسخهٔ بهینهسازی فروشندهٔ دورهگرد.
اگر یک مسئلهٔ NP-کامل در P باشد چه میشود؟
آنوقت P = NP، چون هر مسئلهٔ NP با یک کاهش چندجملهای به آن تبدیل میشود و بعد در زمان چندجملهای حل میشود.
چرا ۲-SAT آسان است ولی ۳-SAT سخت؟
هر بند دوتایی (a ∨ b) را میشود به دو استلزام ¬a → b و ¬b → a تبدیل کرد. فرمول ارضاناپذیر است اگر و فقط اگر متغیری با نقیضش در یک مؤلفهٔ قویاً همبند باشد، که در زمان خطی بررسی میشود. بندهای سهتایی چنین ساختاری ندارند.
برای اثبات NP-کامل بودن یک مسئله چه چیزهایی لازم است؟
دو چیز: اول نشان بده مسئله در NP است، یعنی یک جواب پیشنهادی را در زمان چندجملهای بررسی کن. دوم یک مسئلهٔ NP-کامل شناختهشده را در زمان چندجملهای به آن کاهش بده و نشان بده جوابها در دو طرف یکیاند.
این مبحث در کلاس
من ارشدم را در دانشگاه صنعتی شریف، در نرمافزار با گرایش الگوریتم و محاسبات گرفتم. نظریهٔ NP-کامل و کاهشها بخشی از دورهٔ طراحی الگوریتم من است؛ با ویدیو، جزوهٔ کامل و تستهای حلشده. دورهها بهزودی روی همین سایت منتشر میشوند و ویدیوی رایگان چند جلسه از کلاسهایم هم بهزودی در صفحهٔ ویدیوهای رایگان همین سایت قرار میگیرد.
قدم بعدی تو
این سه گزاره را درست یا نادرست کن: ۱) اگر ۳-SAT را به مسئلهٔ X کاهش دهیم، X در NP است. ۲) مسئلهٔ «آیا گراف ۲-رنگپذیر است؟» NP-کامل است. ۳) اگر بزرگترین مجموعهٔ مستقل یک گراف ۱۰ رأسی ۴ باشد، کوچکترین پوشش رأسی آن ۶ است.
جوابها: ۱) نادرست؛ این کاهش فقط NP-سخت بودن X را نشان میدهد و عضویت در NP جداگانه باید ثابت شود. ۲) نادرست؛ ۲-رنگپذیری یعنی دوبخشی بودن و در P است. ۳) درست؛ مجموع این دو همیشه برابر تعداد رأسهاست.
روش کار را در روش تولید محتوا ببین.
منابع این مطلب
- اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶سازمان سنجش آموزش کشور · بررسی ۱۷ شهریور ۱۴۰۵ · اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶
عنوان دادهساختارها و الگوریتمها در ۱۲۷۷ و ۱۲۷۶ و طراحی الگوریتمها در ۱۲۰۹
سازمان سنجش آموزش کشور — اطلاعیه و جدول مجموعههای امتحانی کارشناسی ارشد ناپیوسته سال ۱۴۰۶