NP مخفف چیست؟

NP مخفف زمان چندجملهای غیرقطعی است. به طور معادل، یک مسئله در NP است اگر یک راهحل پیشنهادی را بتوان در زمان چندجملهای بررسی کرد، حتی اگر یافتن آن دشوار به نظر برسد. مسیر فروشنده دورهگرد با طولی کمتر از یک مقدار معین، پس از ارائه به راحتی قابل تأیید است اما ظاهراً کشف آن دشوار است.

چگونه اثبات میکنید که یک مسئله جدید NP-کامل است؟

شما دو چیز را نشان میدهید: اینکه مسئله در NP است، بنابراین راهحلهای کاندید به سرعت قابل بررسی هستند، و اینکه یک مسئله NP-کامل شناخته شده در زمان چندجملهای به آن کاهش مییابد. این کاهش سختی شناخته شده را منتقل میکند و مسئله جدید را در میان سختترین مسائل NP قرار میدهد.

کامل بودن NP و کاهش‌ها

مسئله NP-کامل یکی از سخت‌ترین مسائل در کلاس NP است، به این معنا که هر مسئله NP به طور کارآمد به آن کاهش می‌یابد، به طوری که حل سریع هر مسئله NP-کامل به تنهایی می‌تواند همه آنها را حل کند.

یافتن موضوع با PaperMindبه‌زودیFind papers & topics

Tools & resources

دریافت اسلایدها

Learn & explore

ویدیوبه‌زودی

Definition

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

Scope

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

Core questions

برای یک مسئله چه معنایی دارد که در میان سخت‌ترین مسائل NP باشد؟
قضیه کوک-لوین چگونه اولین مسئله NP-کامل را شناسایی می‌کند؟
چگونه از کاهش‌ها برای اثبات NP-کامل بودن یک مسئله جدید استفاده می‌شود؟
چرا NP-کامل بودن یک مسئله برای هزاران مسئله دیگر پیامدهایی دارد؟

Key theories

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

Clinical relevance

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

History

کوک در سال ۱۹۷۱ رضایت‌پذیری را NP-کامل اثبات کرد و لوین به طور مستقل نتایج مشابهی را در اتحاد جماهیر شوروی به دست آورد. در سال ۱۹۷۲ کارپ بیست و یک مسئله NP-کامل دیگر را نشان داد که گستردگی این پدیده را آشکار ساخت و NP-کامل بودن را به ابزار اصلی برای تشخیص سختی محاسباتی تبدیل کرد.

Key figures

Stephen Cook
Leonid Levin
Richard Karp

Seminal works

cook1971
karp1972

Frequently asked questions

NP مخفف چیست؟: NP مخفف زمان چندجمله‌ای غیرقطعی است. به طور معادل، یک مسئله در NP است اگر یک راه‌حل پیشنهادی را بتوان در زمان چندجمله‌ای بررسی کرد، حتی اگر یافتن آن دشوار به نظر برسد. مسیر فروشنده دوره‌گرد با طولی کمتر از یک مقدار معین، پس از ارائه به راحتی قابل تأیید است اما ظاهراً کشف آن دشوار است.
چگونه اثبات می‌کنید که یک مسئله جدید NP-کامل است؟: شما دو چیز را نشان می‌دهید: اینکه مسئله در NP است، بنابراین راه‌حل‌های کاندید به سرعت قابل بررسی هستند، و اینکه یک مسئله NP-کامل شناخته شده در زمان چندجمله‌ای به آن کاهش می‌یابد. این کاهش سختی شناخته شده را منتقل می‌کند و مسئله جدید را در میان سخت‌ترین مسائل NP قرار می‌دهد.