چگونه می توان یک تایید کننده زمان چند جمله ای را به یک ماشین تورینگ غیر قطعی معادل تبدیل کرد؟
یک تأیید کننده زمان چند جمله ای را می توان با ساخت ماشینی که می تواند گواهی اثبات را حدس زده و آن را در زمان چند جمله ای تأیید کند، به یک ماشین تورینگ غیر قطعی معادل تبدیل کرد. این تبدیل بر اساس مفهوم محاسبات غیر قطعی است که به ماشین اجازه می دهد تمام مسیرهای ممکن را به طور همزمان کشف کند.
برای درک این تبدیل، اجازه دهید ابتدا تعریف کنیم که تایید کننده زمان چند جمله ای چیست. در تئوری پیچیدگی محاسباتی، تأییدکننده زمان چند جمله‌ای یک ماشین تورینگ قطعی است که می‌تواند صحت یک راه‌حل برای یک مسئله تصمیم‌گیری را در زمان چند جمله‌ای تأیید کند. این دو ورودی می گیرد: نمونه مشکل و گواهی اثبات، و تعیین می کند که آیا گواهی برای نمونه داده شده یک مدرک معتبر است یا خیر.
حال، برای تبدیل یک تایید کننده زمان چند جمله ای به یک ماشین تورینگ غیر قطعی معادل، باید ویژگی های محاسبات غیر قطعی را در نظر بگیریم. در یک ماشین تورینگ غیر قطعی، در هر مرحله، ماشین می تواند در چندین حالت باشد و می تواند به طور همزمان به چندین حالت تبدیل شود. این به ماشین اجازه می دهد تا تمام مسیرهای محاسباتی ممکن را به صورت موازی کشف کند.
برای تبدیل تأییدکننده، می‌توانیم یک ماشین تورینگ غیر قطعی بسازیم که گواهی اثبات را حدس می‌زند و سپس تأییدکننده را در تمام مسیرهای ممکن شبیه‌سازی می‌کند. اگر هر یک از مسیرها قبول کند، ماشین غیر قطعی می پذیرد. در غیر این صورت رد می کند.
اجازه دهید این موضوع را با یک مثال توضیح دهیم. فرض کنید برای مسئله رنگ آمیزی نمودار یک تأیید کننده زمان چند جمله ای داریم. تأیید کننده یک نمودار و رنگ آمیزی رئوس آن را به عنوان ورودی می گیرد و با تأیید اینکه هیچ رئوس مجاور هم رنگی ندارند، معتبر بودن رنگ آمیزی را بررسی می کند.
برای تبدیل این تایید کننده به یک ماشین تورینگ غیر قطعی، ماشینی می سازیم که رنگ آمیزی را حدس می زند و سپس تایید کننده را روی تمام رنگ های ممکن به طور همزمان شبیه سازی می کند. اگر هر یک از رنگ‌ها محدودیت‌های رنگ‌آمیزی را برآورده کند، ماشین غیر قطعی می‌پذیرد. در غیر این صورت رد می کند.
در این مثال، ماشین غیر قطعی یک رنگ آمیزی را با اختصاص رنگ ها به رئوس به صورت موازی حدس می زند. سپس تأیید کننده را در هر یک از رنگ‌های ممکن شبیه‌سازی می‌کند و بررسی می‌کند که آیا رنگ‌آمیزی معتبر است یا خیر. اگر هر یک از شبیه سازی ها بپذیرد، ماشین غیر قطعی می پذیرد.
با استفاده از این تبدیل، می‌توان دید که یک تأییدکننده زمان چند جمله‌ای را می‌توان به یک ماشین تورینگ غیر قطعی معادل تبدیل کرد. این تبدیل به ما اجازه می دهد تا پیچیدگی مسائل را در کلاس NP (زمان چند جمله ای غیر قطعی) با در نظر گرفتن وجود تأیید کننده های زمان چند جمله ای تجزیه و تحلیل کنیم.
یک تأیید کننده زمان چند جمله ای را می توان با ساخت ماشینی که گواهی اثبات را حدس زده و آن را در تمام مسیرهای ممکن به طور همزمان تأیید می کند به یک ماشین تورینگ غیر قطعی معادل تبدیل کرد. این تبدیل به ما امکان می دهد پیچیدگی مسائل را در کلاس NP تجزیه و تحلیل کنیم.
سایر پرسش ها و پاسخ های اخیر در مورد پیچیدگی:
- آیا کلاس PSPACE با کلاس EXPSPACE برابر نیست؟
- آیا کلاس پیچیدگی P زیرمجموعه ای از کلاس PSPACE است؟
- آیا می توانیم با پیدا کردن یک راه حل چند جمله ای کارآمد برای هر مسئله کامل NP در یک TM قطعی ثابت کنیم که کلاس Np و P یکسان هستند؟
- آیا کلاس NP می تواند با کلاس EXPTIME برابر باشد؟
- آیا مشکلاتی در PSPACE وجود دارد که هیچ الگوریتم NP شناخته شده ای برای آنها وجود ندارد؟
- آیا مشکل SAT می تواند یک مشکل کامل NP باشد؟
- اگر یک ماشین تورینگ غیر قطعی وجود داشته باشد که آن را در زمان چند جمله‌ای حل کند، می‌تواند در کلاس پیچیدگی NP باشد؟
- NP کلاس زبان هایی است که تأیید کننده زمان چند جمله ای دارند
- آیا P و NP در واقع کلاس پیچیدگی یکسانی هستند؟
- آیا هر زبان متنی در کلاس پیچیدگی P است؟
سوالات و پاسخ های بیشتر را در Complexity مشاهده کنید