ردههای پیچیدگی زمان و فضا
ردههای پیچیدگی، مسائل تصمیمگیری را بر اساس زمان یا حافظهای که یک ماشین برای حل آنها نیاز دارد، گروهبندی میکنند و محاسبات را در یک چشمانداز ساختاریافته از فضای لگاریتمی تا زمان نمایی سازماندهی میکنند.
Definition
رده پیچیدگی مجموعهای از مسائل است که در یک کران مشخص بر روی یک منبع، معمولاً زمان یا حافظه کاری مورد استفاده توسط یک ماشین تورینگ به عنوان تابعی از طول ورودی، قابل حل هستند، با انواع قطعی و غیرقطعی برای هر منبع.
Scope
این موضوع شامل تعریف ردههای زمان و فضای قطعی و غیرقطعی مانند P، NP، L، NL، PSPACE و EXPTIME، قضایای سلسلهمراتبی که آنها را از هم جدا میکنند، شمولها و روابط شناختهشده بین آنها، قضیه ساویچ در مورد ارتباط فضای غیرقطعی و قطعی، و مسائل کامل که هر رده را مشخص میکنند، میشود.
Core questions
- مسائل چگونه بر اساس زمان و حافظه مورد نیاز برای حل آنها گروهبندی میشوند؟
- کدام شمولها در میان ردههای پیچیدگی استاندارد به طور قطعی شناخته شدهاند؟
- فضای غیرقطعی چگونه با فضای قطعی مرتبط است؟
- مسائل کامل چه نقشی در مشخص کردن یک رده ایفا میکنند؟
Key theories
- قضایای سلسلهمراتب
- با زمان یا فضای مجانبی بیشتر، یک ماشین میتواند زبانهای به مراتب بیشتری را تصمیمگیری کند، بنابراین ردههای زمان و فضا سلسلهمراتب مناسبی را تشکیل میدهند و منابع را نمیتوان بدون از دست دادن مسائل هدر داد.
- قضیه ساویچ
- هر مسئلهای که در فضای غیرقطعی قابل حل باشد، میتواند به صورت قطعی با استفاده از تنها مربع آن فضا حل شود، بنابراین برای حافظه، برخلاف آنچه که ظاهراً برای زمان است، غیرقطعی بودن حداکثر یک مزیت متوسط را فراهم میکند.
Clinical relevance
قرار دادن یک مسئله در یک رده پیچیدگی به متخصصان میگوید که چه انتظاری داشته باشند: مسائل در P به ورودیهای بزرگ مقیاسپذیر هستند، مسائل PSPACE-کامل مانند بسیاری از بازیها و وظایف برنامهریزی در برابر راهحل کارآمد مقاومت میکنند، و ساختار رده راهنمایی میکند که آیا باید به دنبال الگوریتمهای دقیق، تقریبها، یا بازطراحی مسئله بود.
History
هارتمنیس و استیرنز ردههای محدود به زمان را تعریف کردند و قضیه سلسلهمراتب زمان را در سال ۱۹۶۵ اثبات کردند و این رشته را بنیان نهادند. پیچیدگی فضا به موازات آن توسعه یافت، با قضیه ساویچ در سال ۱۹۷۰ و نتایج بعدی مانند بسته شدن فضای غیرقطعی تحت مکمل توسط ایمرمن و سزلپچنی که تصویر را دقیقتر کرد.
Key figures
- Juris Hartmanis
- Richard Stearns
- Walter Savitch
- Stephen Cook
Related topics
Seminal works
- hartmanisStearns1965
- savitch1970
Frequently asked questions
- تفاوت بین پیچیدگی زمانی و فضایی چیست؟
- پیچیدگی زمانی تعداد گامهایی را که یک الگوریتم برمیدارد میشمارد، در حالی که پیچیدگی فضایی حافظه کاری مورد استفاده آن را اندازهگیری میکند. آنها متفاوت عمل میکنند: فضا میتواند در حین انجام محاسبات دوباره استفاده شود، به همین دلیل فضای غیرقطعی نسبت به فضای قطعی قدرت بسیار کمتری دارد تا مقایسه مشابه برای زمان.
- چرا قضایای سلسلهمراتب اهمیت دارند؟
- آنها ثابت میکنند که منابع بیشتر واقعاً امکان حل مسائل بیشتری را فراهم میکنند و احتمال فروپاشی همه ردهها در یک رده را رد میکنند. این امر تضمین میکند، برای مثال، مسائلی وجود دارند که در زمان نمایی قابل حل هستند اما در زمان چندجملهای خیر، که کل بنای ردههای پیچیدگی را لنگر میاندازد.