کامل بودن NP و عدم حل‌پذیری

کامل بودن NP سخت‌ترین مسائل را در کلاس NP شناسایی می‌کند — مسائلی که هر مسئله NP به آن‌ها تقلیل می‌یابد — و چارچوب استانداردی را برای تشخیص مسائلی که هیچ الگوریتم کارآمدی برای آن‌ها شناخته شده یا محتمل نیست، فراهم می‌آورد.

Definition

یک مسئله تصمیم‌گیری NP-کامل است اگر در NP قرار گیرد (نمونه‌های بله آن دارای گواهی‌های قابل تأیید کارآمد باشند) و هر مسئله در NP در زمان چندجمله‌ای به آن تقلیل یابد؛ چنین مسائلی سخت‌ترین مسائل در NP هستند و یک الگوریتم زمان چندجمله‌ای برای هر یک، الگوریتمی برای همه فراهم می‌کند.

Scope

این موضوع کلاس‌های پیچیدگی P و NP، تقلیل‌های زمان چندجمله‌ای، تعاریف NP-سختی و NP-کامل بودن، قضیه کوک-لوین که رضایت‌پذیری را به عنوان NP-کامل معرفی می‌کند، کاتالوگ مسائل NP-کامل کارپ، و پیامدهای عملی عدم حل‌پذیری برای طراحی الگوریتم را پوشش می‌دهد. این مفاهیم را برای شناسایی و مقابله با مسائل دشوار به کار می‌برد؛ نظریه رسمی گسترده‌تر کلاس‌های پیچیدگی محاسباتی در زیرشاخه نظریه محاسبات مورد بررسی قرار می‌گیرد.

Core questions

• چه چیزی کلاس‌های پیچیدگی P و NP را متمایز می‌کند؟
• چگونه یک تقلیل زمان چندجمله‌ای سختی را از یک مسئله به مسئله دیگر منتقل می‌کند؟
• قضیه کوک-لوین چه چیزی را اثبات می‌کند و چرا رضایت‌پذیری محوری است؟
• چگونه یک مسئله جدید با تقلیل از یک مسئله شناخته شده NP-کامل اثبات می‌شود؟
• هنگامی که یک مسئله NP-سخت نشان داده می‌شود، چه استراتژی‌های الگوریتمی باقی می‌مانند؟

Key concepts

• کلاس پیچیدگی P
• کلاس پیچیدگی NP
• تقلیل زمان چندجمله‌ای
• NP-سختی
• NP-کامل بودن
• قضیه کوک-لوین
• رضایت‌پذیری بولی (SAT)
• مسئله P در مقابل NP

Key theories

قضیه کوک-لوین

قضیه کوک-لوین اثبات می‌کند که رضایت‌پذیری بولی (SAT) NP-کامل است: هر مسئله در NP در زمان چندجمله‌ای به آن تقلیل می‌یابد، که اولین مسئله NP-کامل و لنگری برای اثبات سختی سایر مسائل را فراهم می‌کند.

تقلیل‌پذیری بین مسائل ترکیبیاتی

کارپ نشان داد که تقلیل‌های زمان چندجمله‌ای بسیاری از مسائل طبیعی — مانند کلیک، پوشش رأس، چرخه همیلتونی، پارتیشن و دیگران — را به شبکه‌ای از مسائل NP-کامل پیوند می‌دهد، به طوری که هر یک را می‌توان با تقلیل از دیگری سخت اثبات کرد.

Clinical relevance

تشخیص اینکه یک مسئله NP-کامل است، یکی از مفیدترین نتایج عملی در محاسبات است: این به مهندسان می‌گوید که انتظار یک الگوریتم دقیق سریع را نداشته باشند و در عوض از الگوریتم‌های تقریبی، اکتشافی، حل‌کننده‌های دقیق تنظیم شده برای نمونه‌های معمول، یا محدودیت‌ها به موارد خاص قابل حل استفاده کنند. بسیاری از مسائل زمان‌بندی، مسیریابی، بسته‌بندی و طراحی NP-کامل هستند.

History

استفان کوک در سال ۱۹۷۱ مفهوم NP-کامل بودن را معرفی کرد و SAT را NP-کامل اثبات نمود؛ لئونید لوین به طور مستقل به نتایج مشابهی دست یافت. مقاله ریچارد کارپ در سال ۱۹۷۲، ۲۱ مسئله طبیعی را NP-کامل نشان داد و دامنه این چارچوب را تثبیت کرد. کتاب گاری و جانسون در سال ۱۹۷۹ صدها مسئله NP-کامل را فهرست کرد و به مرجع استاندارد تبدیل شد.

Debates

P در مقابل NP

اینکه آیا P برابر NP است — یعنی آیا هر مسئله‌ای که به طور کارآمد قابل تأیید است، به طور کارآمد نیز قابل حل است — مهم‌ترین مسئله حل نشده در این زمینه است؛ تقریباً همه محققان حدس می‌زنند که P برابر NP نیست، اما این سؤال حل نشده باقی مانده و یکی از مسائل جایزه هزاره است.

Key figures

• Stephen Cook
• Richard Karp
• Leonid Levin
• Michael Garey
• David Johnson

Seminal works

• cook1971
• karp1972
• cormen2009

Frequently asked questions

تفاوت بین NP-سخت و NP-کامل چیست؟

یک مسئله NP-سخت است اگر هر مسئله NP در زمان چندجمله‌ای به آن تقلیل یابد، اما لزوماً خود آن در NP نباشد و لزوماً یک مسئله تصمیم‌گیری نباشد. یک مسئله NP-کامل است اگر هم NP-سخت باشد و هم در NP قرار گیرد. مسائل NP-کامل سخت‌ترین مسائلی هستند که هنوز در NP قرار دارند.

آیا NP-کامل بودن به این معنی است که یک مسئله هرگز قابل حل نیست؟

خیر. این بدان معناست که هیچ الگوریتم زمان چندجمله‌ای برای همه ورودی‌ها شناخته شده نیست و احتمالاً هیچ‌کدام وجود ندارد اگر P برابر NP نباشد. در عمل، چنین مسائلی با الگوریتم‌های تقریبی، اکتشافی، حل‌کننده‌های زمان نمایی که روی نمونه‌های واقعی کار می‌کنند، یا با محدود کردن به موارد خاص، حل می‌شوند.