اگر P برابر NP بود چه اتفاقی میافتاد؟

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

چرا حل این مسئله اینقدر دشوار است؟

اثبات برابری P و NP نیازمند یک الگوریتم سریع برای یک مسئله NP-کامل است که هیچکس آن را پیدا نکرده است؛ اثبات تفاوت آنها نیازمند نشان دادن این است که چنین الگوریتمی نمیتواند وجود داشته باشد. نتایج مربوط به نسبیسازی و اثباتهای طبیعی نشان میدهند که تکنیکهای استاندارد ذاتاً قادر به اثبات مورد دوم نیستند، بنابراین رویکردی کاملاً جدید مورد نیاز است.

مسئله P در برابر NP

مسئله P در برابر NP می‌پرسد که آیا هر مسئله‌ای که راه‌حل‌های آن را می‌توان به سرعت تأیید کرد، می‌تواند به سرعت نیز حل شود یا خیر. این سؤال، پرسش اصلی و حل‌نشده علوم نظری کامپیوتر و یکی از مسائل جایزه هزاره کِلِی است.

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

Tools & resources

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

Learn & explore

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

Definition

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

Scope

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

Core questions

آیا یافتن یک راه‌حل اساساً دشوارتر از بررسی آن است؟
چرا پاسخ به این بستگی دارد که آیا هر مسئله NP-کامل در P قرار دارد یا خیر؟
اگر P برابر NP بود و اگر نبود، جهان چگونه به نظر می‌رسید؟
چرا دهه‌ها تلاش نتوانسته است این سؤال را حل کند؟

Key theories

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

Clinical relevance

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

History

کوک این سؤال را در سال ۱۹۷۱ در کنار NP-کامل بودن مطرح کرد و به سرعت به عنوان یک مسئله بنیادی شناخته شد. تلاش‌ها از طریق کران‌های پایین مداری در دهه ۱۹۸۰ با مانع اثبات‌های طبیعی که توسط رازبروف و رودیچ شناسایی شد، مواجه گشت، و در سال ۲۰۰۰ مؤسسه ریاضیات کِلِی آن را به عنوان یکی از مسائل جایزه هزاره با جایزه یک میلیون دلاری معرفی کرد.

Debates

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

Key figures

Stephen Cook
Leonid Levin
Richard Karp
Alexander Razborov

Seminal works

cook1971
aroraBarak2009

Frequently asked questions

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