نظریه پیچیدگی محاسباتی
نظریه پیچیدگی محاسباتی مسائل را بر اساس میزان زمان، حافظه و سایر منابعی که هر الگوریتم برای حل آنها نیاز دارد، طبقهبندی میکند و خطوط مشخصی بین آنچه به طور کارآمد قابل حل است و آنچه به نظر میرسد غیرقابل حل است، ترسیم میکند.
Definition
نظریه پیچیدگی محاسباتی، دشواری ذاتی مسائل محاسباتی را که با منابع، عمدتاً زمان اجرا و حافظه، مورد نیاز برای حل آنها بر روی مدلی مانند ماشین تورینگ اندازهگیری میشود، مطالعه میکند و مسائل را بر این اساس در کلاسهای پیچیدگی گروهبندی میکند.
Scope
این حوزه شامل کلاسهای پیچیدگی زمانی و فضایی مانند P، NP، PSPACE و سلسلهمراتب چندجملهای، نظریه NP-کامل بودن و کاهشهای زمان چندجملهای، مسئله مرکزی P در مقابل NP، و مدلهای محدود به منابع شامل تصادفی بودن، تعامل و اثباتها، همراه با نتایج سلسلهمراتب و سختی که این کلاسها را به هم مرتبط میکند، میشود.
Sub-topics
Core questions
- حل یک مسئله معین ذاتاً به چه مقدار زمان و حافظه نیاز دارد؟
- کدام مسائل را میتوان به طور کارآمد حل کرد و کدامها به نظر میرسد در برابر همه الگوریتمهای کارآمد مقاومت میکنند؟
- چگونه نشان داده میشود که مسائل به اندازه سختترین اعضای یک کلاس پیچیدگی دشوار هستند؟
- آیا تصادفی بودن، تعامل یا عدم قطعیت قدرت محاسباتی واقعی را اضافه میکنند؟
Key theories
- قضایای سلسلهمراتب زمان و فضا
- با داشتن زمان یا فضای به مراتب بیشتر، ماشینها میتوانند مسائل به مراتب بیشتری را حل کنند، که اثبات میکند کلاسهای پیچیدگی سلسلهمراتب واقعی را تشکیل میدهند و برخی مسائل ذاتاً دشوارتر از بقیه هستند.
- NP-کامل بودن
- قضیه کوک-لوین مسائلی را در NP شناسایی میکند که هر مسئله NP دیگری به آنها کاهش مییابد، بنابراین یک الگوریتم کارآمد واحد برای هر یک از آنها، همه آنها را به طور کارآمد حل خواهد کرد.
- مدلهای محدود به منابع
- افزودن تصادفی بودن، تعامل یا تناوب، کلاسهایی مانند BPP، IP و سلسلهمراتب چندجملهای را تعریف میکند، که روابط آنها تصویر آنچه منابع اضافی میتوانند و نمیتوانند به دست آورند را واضحتر میکند.
Clinical relevance
نظریه پیچیدگی با تأیید اینکه کدام مسائل الگوریتمهای کارآمد را میپذیرند و کدامها NP-سخت هستند و بنابراین بهتر است با روشهای اکتشافی یا تقریبی مورد حمله قرار گیرند، عمل را هدایت میکند؛ سختی مفروض برخی مسائل نیز زیربنای رمزنگاری مدرن است، که امنیت آن بر وظایفی استوار است که از نظر محاسباتی غیرممکن تلقی میشوند.
History
هارتمنیس و استرنز این رشته را در سال ۱۹۶۵ با تعریف کلاسهای پیچیدگی و اثبات قضایای سلسلهمراتبی پایهگذاری کردند. کوک و لوین در حدود سال ۱۹۷۱ مفهوم NP-کامل بودن را معرفی کردند، کارپ در سال ۱۹۷۲ بسیاری از مسائل طبیعی را کامل نشان داد، و دهههای بعدی مدلهای اثبات تصادفی، تعاملی و قابل بررسی احتمالی را اضافه کردند.
Key figures
- Stephen Cook
- Richard Karp
- Leonid Levin
- Juris Hartmanis
Related topics
Seminal works
- cook1971
- hartmanisStearns1965
- aroraBarak2009
Frequently asked questions
- تفاوت بین محاسبهپذیری و پیچیدگی چیست؟
- محاسبهپذیری میپرسد که آیا یک مسئله را میتوان با هر الگوریتمی حل کرد، بدون توجه به هزینه. پیچیدگی فرض میکند که مسئله قابل حل است و میپرسد که آن راهحل چقدر باید از نظر زمان و حافظه پرهزینه باشد، و تمایزات ظریفتری را بین مسائلی که اصولاً قابل حل هستند، ترسیم میکند.
- چرا NP-کامل بودن در عمل اهمیت دارد؟
- هنگامی که یک مسئله NP-کامل نشان داده میشود، به هزاران مسئله دیگر گره میخورد که با وجود دههها تلاش، هیچ الگوریتم کارآمدی برای آنها شناخته نشده است. این نشان میدهد که جستجوی یک الگوریتم دقیق و سریع احتمالاً بیفایده است و روشهای تقریبی، اکتشافی یا موارد خاص مسیر واقعبینانه هستند.