چرا برخی مسائل هیچ الگوریتم کارآمد شناختهشدهای ندارند
هر الگوریتمی که تاکنون در این مجموعه پوشش داده شده — مرتبسازی، کوتاهترین مسیرها، درختهای پوشای کمینه — در زمان چندجملهای اجرا میشود، به این معنا که زمان اجرایش توسط برخی تابع چندجملهای از اندازه ورودی محدود است. اما یک دسته بزرگ و از نظر عملی مهم از مسائل هیچ الگوریتم زمان-چندجملهای شناختهشدهای ندارند، با وجود دههها تلاش پژوهشگران در سراسر جهان. این مقاله نظریهای که این مسائل را طبقهبندی میکند و توضیح میدهد چرا سختی ظاهریشان صرفاً یک موضوع زیرکی ناکافی نیست را توضیح میدهد.
کلاس پیچیدگی P
P کلاس مسائل تصمیم (مسائل با یک پاسخ بله/خیر) قابلحل توسط یک الگوریتم قطعی در زمان چندجملهای است. هر الگوریتمی که در سراسر این مجموعه بحث شد — مرتبسازی در O(n log n)، کوتاهترین مسیرها در O(VE) یا بهتر، درختهای پوشای کمینه در O(E log V) — یک مسئله در P را حل میکند. مسائل در P معمولاً Tractable (قابلحل عملی) در نظر گرفته میشوند، به این معنا که حتی برای ورودیهای بزرگ عملاً قابلحل هستند.
کلاس پیچیدگی NP
NP مخفف "Nondeterministic Polynomial time" است، اما بهطور شهودیتر از طریق مفهوم Verification (تأیید) درک میشود: یک مسئله در NP است اگر، با داشتن یک راهحل پیشنهادی (به نام یک Certificate (گواهی))، آن راهحل بتواند در زمان چندجملهای درست تأیید شود، حتی اگر یافتن راهحل از ابتدا ممکن است بسیار سختتر باشد.
مثال: مسئله چرخه همیلتونی
(آیا یک گراف شامل یک چرخه است که دقیقاً یکبار از هر رأس بازدید میکند؟)
یافتن چنین چرخهای از ابتدا ممکن است نیازمند
بررسی تعداد نمایی ترتیبهای ممکن باشد
اما تأیید یک چرخه پیشنهادی بدیهی است:
صرفاً بررسی کن که دقیقاً یکبار از هر رأس بازدید میکند
و اینکه رأسهای پیاپی در چرخه پیشنهادی
واقعاً توسط یالها متصلاند — این فقط زمان O(V) میگیرداز آنجا که مسائل P واضحاً میتوانند در زمان چندجملهای تأیید شوند (صرفاً دوباره از ابتدا حلشان کن، که از قبل سریع است)، هر مسئله در P نیز در NP است، که رابطه P ⊆ NP را میدهد. پرسش باز معروف، P vs. NP، میپرسد آیا این احتوا دقیق است — آیا مسائلی در NP وجود دارند که در P نیستند، به این معنا که بهسرعت قابلتأیید اما بهسرعت قابلحل نیستند.
تقلیلها: مقایسه سختی مسئله
یک Polynomial-Time Reduction (تقلیل زمان-چندجملهای) از مسئله A به مسئله B یک الگوریتم زمان-چندجملهای است که هر نمونه از A را به یک نمونه معادل از B تبدیل میکند، طوریکه پاسخ به نمونه تبدیلشده B همان پاسخ به نمونه اصلی A است.
اگر A در زمان چندجملهای به B تقلیل یابد (نوشتهشده A ≤ₚ B)،
این یعنی: اگر B بتواند در زمان چندجملهای حل شود،
آنگاه A نیز میتواند در زمان چندجملهای حل شود
(صرفاً A را به B تقلیل بده، سپس B را حل کن)
بهطور معادل: اگر A نتواند در زمان چندجملهای حل شود،
آنگاه B نیز نمیتواند در زمان چندجملهای حل شود
(در غیر این صورت A میتوانست از طریق تقلیل حل شود)تقلیلها ابزار بنیادین برای مقایسه سختی نسبی مسائل هستند: یک تقلیل از A به B نشان میدهد B "حداقل بههماناندازه سخت" A است، چون هر الگوریتمی برای B بلافاصله یک الگوریتم برای A تولید میکند.
NP-Hardness و NP-Completeness
یک مسئله H NP-Hard است اگر هر مسئله در NP بتواند در زمان چندجملهای به آن تقلیل یابد — به این معنا که H حداقل بههماناندازه سخت هر مسئله در NP است. یک مسئله NP-Complete است اگر هم NP-hard باشد و هم خودش عضوی از NP باشد.
مسائل NP-Complete، بهطور غیررسمی، "سختترین"
مسائل در NP هستند: اگر هر مسئله NP-complete منفردی
بتواند در زمان چندجملهای حل شود، آنگاه هر
مسئله در NP نیز میتواند در زمان چندجملهای حل شود،
که P = NP را اثبات میکنداین چرایی این است که NP-completeness یک طبقهبندی اینقدر معناداری است: سختی یک مسئله منفرد را به حلشدن کل پرسش P در مقابل NP، یکی از مهمترین مسائل باز در تمام علوم کامپیوتر و ریاضیات، متصل میکند.
قضیه کوک-لوین: اولین مسئله NP-Complete
ایجاد اینکه هر مسئلهای NP-complete است ابتدا بهنظر میرسد دوری باشد — چگونه یک مسئله میتواند نشان داده شود حداقل بههماناندازه سخت "هر مسئله در NP" است بدون بررسی جداگانه بینهایت مسئله؟ قضیه پیشگامانه Cook-Levin Theorem این را با اثبات مستقیم اینکه SAT (مسئله رضایتپذیری بولی: با داشتن یک فرمول بولی، آیا برخی انتساب مقادیر درست/نادرست به متغیرهایش کل فرمول را درست میکند؟) NP-complete است، با استفاده از یک ساخت مستقیم مبتنی بر تعریف رسمی یک ماشین تورینگ، حل کرد.
ساخت شبکه مسائل NP-Complete از طریق تقلیلها
وقتی یک مسئله شناختهشده NP-complete باشد، اثبات اینکه یک مسئله جدید X NP-complete است دیگر نیازمند این ساخت بنیادین نیست. در عوض، فقط نیازمند دو گام است.
برای اثبات NP-complete بودن مسئله X:
گام ۱: نشان بده X در NP است
(یک راهحل پیشنهادی برای X میتواند در زمان چندجملهای تأیید شود)
گام ۲: نشان بده برخی مسئله NP-complete شناختهشده Y
در زمان چندجملهای به X تقلیل مییابد (Y ≤ₚ X)
(این نشان میدهد X حداقل بههماناندازه سخت Y است،
و از آنجا که Y حداقل بههماناندازه سخت هر چیزی در NP است،
X نیز باید باشد)این چگونگی ساخت لیست عظیم و دائماً-در-حال-رشد هزاران مسئله NP-complete شناختهشده است: با شروع از SAT، هر مسئله جدید از طریق یک زنجیره تقلیل به SAT (یا به یک مسئله دیگر ازقبل-اثباتشده NP-complete) متصل میشود، و یک شبکه از سختی بههممتصل تشکیل میدهد. مسائل NP-complete شناختهشده شامل مسئله فروشنده دورهگرد، مسئله کولهپشتی، رنگآمیزی گراف، و مسئله چرخه همیلتونی که پیشتر در این مقاله ذکر شد.
چرا NP-Completeness در عمل اهمیت دارد
وقتی با یک مسئله بهینهسازی جدید و بهظاهر سخت مواجه میشویم، اثبات NP-complete بودن آن صرفاً یک تمرین آکادمیک نیست — راهنمای عملی و واقعاً قابلاقدامی فراهم میکند. این نشان میدهد، با پشتیبانی نظری قوی (هرچند نه اثبات مطلق، چون P در مقابل NP همچنان حلنشده باقی میماند)، که جستجو برای یک الگوریتم کارآمد، دقیق، و زمان-چندجملهای بهاحتمال زیاد بیفایده است، و تلاش بهتر است روی رویکردهای جایگزین صرف شود: الگوریتمهای تقریبی که یک راهحل بهطور اثباتپذیر نزدیک-به-بهینه را سریع پیدا میکنند، ابتکارهایی که در عمل بدون تضمینهای بدترینحالت خوب کار میکنند، یا الگوریتمهای دقیقی که بدترینحالت نماییشان قابلقبول است چون اندازههای ورودی دنیای واقعی بهاندازه کافی کوچک باقی میمانند.
چرا این نظریه فراتر از مسائل منفرد اهمیت دارد
نظریه NP-completeness نحوه رویکرد دانشمندان کامپیوتر به مسائل سخت را متحول کرد: بهجای جستجوی بیپایان برای یک الگوریتم کارآمد ناموجود (که یکی از معروفترین پرسشهای باز ریاضی را حل میکرد اگر پیدا میشد)، متخصصان میتوانند بهسرعت مسائل NP-hard را از طریق تقلیل تشخیص دهند و تلاش را بهسمت تکنیکهای جایگزین عملی که در بالا ذکر شد هدایت کنند، که چندتای آنها در الگوریتمهای تقریبی که بعداً در این مجموعه پوشش داده میشوند بررسی میشوند.