اگر یک ماشین تورینگ غیر قطعی وجود داشته باشد که آن را در زمان چند جملهای حل کند، میتواند در کلاس پیچیدگی NP باشد؟
سوال "اگر یک ماشین تورینگ غیر قطعی وجود داشته باشد که آن را در زمان چند جمله ای حل کند می تواند در کلاس پیچیدگی NP باشد؟" مفاهیم اساسی در نظریه پیچیدگی محاسباتی را لمس می کند. برای پرداختن به این سوال به طور جامع، باید تعاریف و ویژگی های کلاس پیچیدگی NP و نقش ماشین های تورینگ غیر قطعی (NDTMs) را در نظر بگیریم.
تعریف NP
کلاس NP (زمان چند جمله ای غیر قطعی) شامل مسائل تصمیم گیری است که یک راه حل داده شده را می توان در زمان چند جمله ای درست یا نادرست توسط یک ماشین تورینگ قطعی (DTM) تأیید کرد. به طور رسمی، اگر یک الگوریتم تأیید چند جملهای وجود داشته باشد که بتواند صحت یک گواهی (یا شاهد) را برای نمونهای از مشکل تأیید کند، یک مشکل تصمیم در NP است.
ماشین های تورینگ غیر قطعی
ماشین تورینگ غیر قطعی یک مدل نظری از محاسبات است که قابلیتهای یک ماشین تورینگ قطعی را گسترش میدهد. بر خلاف یک DTM که یک مسیر محاسباتی منفرد تعریف شده توسط تابع انتقال آن را دنبال می کند، یک NDTM می تواند چندین مسیر محاسباتی را به طور همزمان دنبال کند. در هر مرحله، یک NDTM میتواند از میان مجموعهای از انتقالهای احتمالی «انتخاب» کند و بهطور مؤثر بسیاری از محاسبات ممکن را به صورت موازی بررسی کند.
حل پذیری زمان چند جمله ای توسط NDTMs
اگر یک الگوریتم غیر قطعی وجود داشته باشد که بتواند در چند مرحله راه حلی برای مسئله پیدا کند که اندازه ورودی چند جمله ای باشد، به یک مسئله در زمان چند جمله ای قابل حل است. این بدان معنی است که برای هر نمونه ای از مسئله، NDTM می تواند یک مسیر محاسباتی را که به یک راه حل در زمان چند جمله ای منتهی می شود، کشف کند.
رابطه بین NP و NDTMs
کلاس NP را می توان به طور معادل بر حسب NDTMs تعریف کرد. به طور خاص، یک مسئله تصمیم در NP است اگر و تنها در صورتی که یک NDTM وجود داشته باشد که بتواند مشکل را در زمان چند جمله ای حل کند. این هم ارزی از این واقعیت ناشی می شود که یک NDTM می تواند گواهی را به صورت غیر قطعی حدس بزند و سپس آن را به صورت قطعی در زمان چند جمله ای تأیید کند.
برای توضیح این موضوع با یک مثال، مسئله شناخته شده NP-complete، مسئله رضایت پذیری بولی (SAT) را در نظر بگیرید. با توجه به فرمول بولی به شکل نرمال ربطی (CNF)، وظیفه تعیین این است که آیا تخصیصی از مقادیر صدق به متغیرهایی وجود دارد که فرمول را درست میکند یا خیر. یک NDTM میتواند SAT را در زمان چند جملهای با حدس زدن غیر قطعی یک انتساب مقادیر صدق و سپس بررسی قطعی اینکه آیا تخصیص با فرمول مطابقت دارد، حل کند. مرحله تأیید، که شامل ارزیابی فرمول تحت تکلیف حدس زده شده است، می تواند در زمان چند جمله ای انجام شود.
مفاهیم حلپذیری زمان چند جملهای توسط NDTMs
با توجه به تعاریف بالا و هم ارزی بین NP و حل پذیری زمان چند جمله ای توسط NDTMs، می توانیم نتیجه بگیریم که اگر یک NDTM وجود داشته باشد که یک مسئله را در زمان چند جمله ای حل کند، در واقع مشکل در NP است. این به این دلیل است که وجود چنین NDTM نشان می دهد که یک الگوریتم تأیید زمان چند جمله ای برای مشکل وجود دارد. مرحله حدس غیر قطعی NDTM مربوط به تولید یک گواهی است و مرحله تأیید قطعی مربوط به الگوریتم تأیید زمان چند جمله ای است.
ملاحظات و مثال های بیشتر
برای توضیح بیشتر این مفهوم، اجازه دهید مثالهای دیگری از مشکلات در NP و رابطه آنها با NDTMs را در نظر بگیریم:
1. مشکل مسیر همیلتونی: با توجه به یک نمودار، مسئله مسیر همیلتونی می پرسد که آیا مسیری وجود دارد که دقیقاً یک بار از هر رأس بازدید کند. یک NDTM می تواند این مشکل را در زمان چند جمله ای با حدس زدن غیر قطعی دنباله ای از رئوس و سپس تأیید اینکه آیا دنباله یک مسیر همیلتونی معتبر را تشکیل می دهد، حل کند. مرحله تأیید شامل بررسی مجاورت رئوس متوالی و اطمینان از اینکه هر راس دقیقاً یک بار بازدید شده است، که هر دو را می توان در زمان چند جمله ای انجام داد.
2. مشکل جمع زیر مجموعه: با توجه به مجموعه ای از اعداد صحیح و یک مجموع هدف، مسئله Subset Sum می پرسد که آیا زیر مجموعه ای از اعداد صحیح وجود دارد که با هدف جمع می شوند یا خیر. یک NDTM می تواند این مشکل را در زمان چند جمله ای با حدس زدن غیر قطعی زیرمجموعه ای از اعداد صحیح و سپس بررسی اینکه آیا مجموع زیر مجموعه با هدف برابر است یا خیر حل کند. مرحله تایید شامل جمع کردن عناصر زیرمجموعه حدس زده شده است که می تواند در زمان چند جمله ای انجام شود.
3. مشکل رنگ آمیزی نمودار: با توجه به یک نمودار و تعدادی رنگ، مسئله Graph Coloring می پرسد که آیا می توان رئوس نمودار را طوری رنگ کرد که هیچ دو راس مجاور هم رنگ را به اشتراک نگذارند؟ یک NDTM میتواند این مشکل را در زمان چند جملهای با تخصیص غیر قطعی رنگها به راسها و سپس تأیید صحت رنگآمیزی حل کند. مرحله تأیید شامل بررسی رنگ رئوس مجاور است که می تواند در زمان چند جمله ای انجام شود.
نتیجه
در پرتو تعاریف و مثالهای ارائه شده، واضح است که اگر یک ماشین تورینگ غیر قطعی وجود داشته باشد که آن را در زمان چند جملهای حل کند، یک مشکل میتواند در کلاس پیچیدگی NP باشد. این رابطه سنگ بنای نظریه پیچیدگی محاسباتی است و بر هم ارزی بین حل پذیری زمان چند جمله ای توسط NDTMs و عضویت در کلاس NP تاکید می کند.
سایر پرسش ها و پاسخ های اخیر در مورد پیچیدگی:
- آیا کلاس PSPACE با کلاس EXPSPACE برابر نیست؟
- آیا کلاس پیچیدگی P زیرمجموعه ای از کلاس PSPACE است؟
- آیا می توانیم با پیدا کردن یک راه حل چند جمله ای کارآمد برای هر مسئله کامل NP در یک TM قطعی ثابت کنیم که کلاس Np و P یکسان هستند؟
- آیا کلاس NP می تواند با کلاس EXPTIME برابر باشد؟
- آیا مشکلاتی در PSPACE وجود دارد که هیچ الگوریتم NP شناخته شده ای برای آنها وجود ندارد؟
- آیا مشکل SAT می تواند یک مشکل کامل NP باشد؟
- NP کلاس زبان هایی است که تأیید کننده زمان چند جمله ای دارند
- آیا P و NP در واقع کلاس پیچیدگی یکسانی هستند؟
- آیا هر زبان متنی در کلاس پیچیدگی P است؟
- آیا بین تعریف NP بهعنوان یک کلاس از مسائل تصمیمگیری با تأییدکنندههای زمان چندجملهای و این واقعیت که مسائل کلاس P دارای تأییدکنندههای زمان چندجملهای نیز هستند، تناقضی وجود دارد؟
سوالات و پاسخ های بیشتر را در Complexity مشاهده کنید