ماشین اوراکل

در نظریه پیچیدگی و نظریه محاسبه‌پذیری، ماشین اوراکل (یا ماشین سروش) یک ماشین انتزاعی برای مطالعه مسائل تصمیم است. می‌توان آن‌را به عنوان ماشین تورینگ همراه با یک جعبه سیاه ،که به آن اوراکل گفته می‌شود، در نظر گرفت که قادر به تصمیم‌گیری مسائل تصمیم خاصی در یک تک‌اقدام است. مسئله می‌تواند از هر رده پیچیدگی باشد. حتی مسائل تصمیم‌ناپذیر، مثل مسئله توقف، می‌توانند استفاده شوند.
اوراکل‌ها
ماشین اوراکل را می‌توان یک ماشین تورینگ متصل به یک اوراکل تصور کرد. اوراکل، در این مبحث، موجودیتی قادر به حل یک سری مسائل است، که به عنوان مثال می‌تواند مسئله تصمیم یا مسئله تابع باشد. مسئله ممکن است محاسبه‌پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامه کامپیوتری تلقی نمی‌شود. اوراکل به طور ساده یک «جعبه سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئله محاسباتی است:
یک مسئله تصمیم به صورت مجموعه A از اعداد طبیعی (یا رشته‌ها) بیان می‌شود. یک نمونه از مسئله یک عدد طبیعی (یا رشته)ی دل‌خواه است. پاسخ به این نمونه در صورتی که عدد (یا رشته) عضو این مجموعه باشد «بله» و در غیر این صورت «نه» می‌باشد.
مسئله تابع به صورت یک تابع f از اعداد طبیعی (یا رشته‌ها) به اعداد طبیعی (یا رشته‌ها) بیان می‌شود. یک نمونه از این مسئله یک ورودی x برای f؛ و پاسخ آن مقدار (f(x است.
یک ماشین اوراکل می‌تواند تمام اعمال معمول یک ماشین تورینگ را به انجام برساند، و هم‌چنین می‌تواند از اوراکل برای به دست آوردن پاسخی برای هر نمونه از مسئله محاسباتی برای آن اوراکل بهره ببرد. برای مثال اگر مسئله یک مسئله تصمیم بر روی یک مجموعه A از اعداد طبیعی باشد، ماشین اوراکل یک عدد طبیعی به اوراکل عرضه می‌دارد، و اوراکل بسته به این که آن عدد عضو A باشد با «بله» یا «نه» پاسخ می‌دهد.
تعاریف
تعاریف هم‌ارز متعددی برای ماشین تورینگ اوراکل وجود دارد، که در پایین در مورد آن‌ها بحث شده است. موردی که این‌جا ارائه شده است از van Melkebeek است (۲۰۰۰:۴۳).
یک ماشین اوراکل مانند یک ماشین تورینگ شامل اجزای زیر است:
یک نوار کار : دنباله‌ای از خانه‌ها بدون شروع یا انتها، که هر کدام می‌تواند شامل یک B (برای خانه خالی) یا یک نماد از الفبای نوار باشد؛
یک هد خواندن/نوشتن ، که بر روی یک خانه از نوار کار می‌ایستد و می‌تواند داده آن را بخواند، داده جدید بنویسد، و بر روی نوار به راست یا چپ حرکت کند؛
یک سازوکار کنترلی ، که می‌تواند در یکی از متناهی تعداد حالت‌هایش باشد، و بسته به حالت فعلی و داده خوانده‌شده اعمال متفاوتی (خواندن داده، نوشتن داده، حرکت سازوکار کنترلی، و تغییر حالت‌ها) را انجام می‌دهد.
علاوه بر این اجزا، یک ماشین اوراکل شامل اجزای زیر نیز هست:
یک نوار اوراکل ، که نواری نیمه‌نامتناهی جدای از نوار کار است. الفبای نوار اوراکل می‌تواند متفاوت از الفبای نوار کار باشد؛
یک هد اوراکل که، همانند هد خواندن/نوشتن، می‌تواند روی نوار اوراکل به چپ یا راست حرکت کرده و نمادها را بخواند یا بنویسد؛
دو حالت ویژه: حالت پرسش و حالت پاسخ.
گاه‌به‌گاه، ماشین اوراکل ممکن است وارد حالت پرسش شود. هنگام این رخ‌داد، اعمال زیر در یک مرحله محاسباتی انجام می‌شوند:
محتویات نوار پرس‌وجو به عنوان یک نمونه از مسئله محاسباتی اوراکل دیده می‌شود؛
پس از مشورت با اوراکل، محتویات نوار پرس‌وجو با پاسخ آن نمونه از مسئله جای‌گزین می‌شود؛
هد اوراکل به اولین خانه از نوار اوراکل منتقل می‌شود؛
حالت ماشین اوراکل به وضعیت پاسخ تغییر می‌یابد.
بنابراین تاثیر تغییر به حالت پرسش، گرفتن پاسخ، در یک مرحله، به نمونه‌ای از مسئله است که بر روی نوار اوراکل نوشته شده است.
تعاریف جای‌گزین
علاوه بر تعریفی که در بالا ارائه شد تعاریف جای‌گزین دیگری نیز وجود دارند. تعدادی از آن‌ها خاص موردی هستند که اوراکل یک مسئله تصمیم را حل می‌کند. در این مورد:
در بعضی تعاریف، به جای نوشتن پاسخ در نوار اوراکل، دو حالت خاص بله و خیر علاوه بر حالت پرسش وجود دارد. وقتی اوراکل مورد مشورت قرار می‌گیرد، حالت بله انتخاب می‌شود اگر محتویات نوار اوراکل درون مجموعه اوراکل باشد، و حالت خیر انتخاب می‌شود اگر محتویات درون مجموعه اوراکل نباشد (Adachi ۱۹۹۰:۱۱۱).
بعضی تعاریف از نوار اوراکل مجزا خودداری می‌کنند. هنگامی که وارد حالت اوراکل می‌شویم، یک نماد نوار مشخص می‌شود. تعداد دفعاتی که این نماد روی نوار کار ظاهر شده‌است از اوراکل پرسیده می‌شود. اگر آن عدد درون مجموعه اوراکل باشد، حالت بعدی حالت بله است؛ در غیر این صورت، حالت بعدی حالت خیر است (Rogers ۱۹۶۷:۱۲۹).
تعریف جای‌گزین دیگر نوار اوراکل را فقط‌خواندنی می‌کند، و حالت‌های پرسش و پاسخ را به طور کلی حذف می‌کند. قبل از شروع به کار ماشین، تابع مشخصه‌ی مجموعه اوراکل با استفاده از نمادهای ۰ و ۱ روی نوار اوراکل نوشته می‌شود. پس از آن ماشین قادر است تا با پیدا کردن خانه مناسب بر روی نوار اوراکل و خواندن مقدار ازقبل نوشته‌شده در آن، از اوراکل پرس‌وجو کند (Soare ۱۹۸۷:۴۷، Rogers ۱۹۶۷:۱۳۰).
این تعاریف از منظر محاسبه‌پذیری تورینگ معادل هستند: تابعی که تحت اوراکل یکی از این تعاریف، اوراکل‌محاسبه‌پذیر باشد، تحت هر دیگری نیز اوراکل‌محاسبه‌پذیر است. هرچند از منظر پیچیدگی محاسباتی، این تعاریف معادل نیستند. تعریفی مانند آن‌چه که van Melkebeek ارائه داده‌بود، که در آن از نوار اوراکلی که ممکن است الفبای خود را داشته باشد استفاده می‌شود، در حالت عمومی لازم است.
کلاس‌های پیچیدگی ماشین اوراکل
کلاس پیچیدگی مسائل تصمیم حل‌پذیر توسط الگوریتمی در کلاس A با استفاده از اوراکلی برای زبان A L ، L نامیده می‌شود. به طور مثال، P SAT کلاس مسائل حل‌پذیر در زمان چندجمله‌ای توسط یک ماشین تورینگ قطعی با اوراکلی برای مسئله ارضاپذیری بولی (SAT) است. نمادگذاری A B را می‌توان برای مجموعه زبان‌های B (یا کلاس پیچیدگی B)، با استفاده از تعریف زیر، تعمیم داد:
زمانی که یک زبان L برای کلاس B کامل باشد، آن‌گاه A L =A B در صورتی که ماشین‌های درون A بتوانند تقلیل‌های استفاده‌شده در تعریف کامل بودن کلاس B را اجرا نمایند. به طور خاص، از آن‌جایی که مسئله ارضاپذیری بولی نسبت به تقلیل‌های زمان چندجمله‌ای ان‌پی کامل است، P SAT =P NP . هرچند، اگر A=DLOGTIME (کلاس مسائل حل‌پذیر در زمان لگاریتمی توسط ماشین تورینگ قطعی)، آن‌گاه A SAT ممکن است برابر با A NP نباشد.
واضح است که NP ⊆ P NP ، ولی این پرسش که آیا NP، P NP ، NP NP و P برابر هستند یا نه، در بهترین حالت عملی باقی می‌مانند. باور بر تفاوت آن‌هاست و این باعث تعریف سلسله‌مراتب چندجمله‌ای می‌شود.
ماشین‌های اوراکل، با در نظر گرفتن رابطه بین P A و NP A برای یک اوراکل A، برای بررسی رابطه بین کلاس‌های پیچیدگی P و NP مفید هستند. به طور خاص، نشان داده شده است که وجود دارند زبان‌های A و B، به قسمی که P A =NP A و (Gill P B ≠NP B ، Baker و Solovay 1975). این حقیقت که پرسش P = NP از هر دو جهت به صورت نسبی است، به این دلیل است که پاسخ به این پرسش دشوار است، زیرا تکنیک اثباتی که به صورت نسبی انجام می‌گیرد (بدون تاثیر گرفتن از اضافه شدن یک اوراکل) نمی‌تواند به پرسش P = NP پاسخ دهد. بسیاری از تکنیک‌های اثبات از نسبی سازی استفاده می‌کنند.
در نظر گرفتن حالتی که یک اوراکل از میان تمام اوراکل‌های ممکن(یک مجموعه بینهایت) به صورت تصادفی انتخاب شود، قابل توجه است. در این حالت نشان داده شده است که با احتمال یک، P A ≠NP A (Bennet و Gill 1981). هنگامی که پاسخ سوالی برای همه اوراکل‌ها درست باشد، در آن صورت پاسخ پرسش برای یک اوراکل تصادفی نیز درست است. این انتخاب اصطلاحات با دانستن این حقیقت که اوراکل‌های تصادفی یک عبارت را فقط با احتمال 1 یا 0 تایید می‌کنند، قابل توجیه است. (این از روی قانون یک‌صفر Kolmogorov بدست می‌آید.) به عنوان یک گواه P≠NP. یک عبارت ممکن است همزمان برای یک اوراکل تصادفی درست و برای یک ماشین تورینگ عادی غلط باشد؛ برای مثال برای اوراکل‌های A، IP A ≠PSPACE A ، در حالی که IP = PSPACE (Chang et al، 1994).
اوراکل‌ها و مسئله پایان‌پذیری
ممکن است که وجود اوراکلی را فرض کرد که قادر به محاسبه یک تابع محاسبه‌ناپذیر باشد، مانند پاسخ به مسئله توقف یا مسائل مشابه دیگر. ماشینی با چنین اوراکلی یک فراکامپیوتر است.
به طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این ماشین‌ها نیز صدق می‌کند؛ با وجود اینکه این ماشین‌ها می‌توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی‌های خاصی به حالت پایان خواهد رسید، به طور کلی، آنها نمی‌توانند تعیین کنند که آیا ماشین‌های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین‌ها به نام سلسله مراتب محاسباتی می‌شود، که هر رده دارای اوراکل پایان‌پذیری قوی‌تر و مسئله پایان‌پذیری قوی‌تری است.
کاربردها در رمزنگاری
در رمزنگاری، اوراکل‌ها برای استدلال در مورد امنیت قراردادهای رمزنگاری که در آنها یک تابع درهم‌ساز استفاده شده است، به کار می‌رود. یک کاهش امنیت برای یک قرارداد در حالتی داده می‌شود که، به جای یک تابع درهم‌ساز، یک اوراکل تصادفی به هر درخواست به صورت تصادفی ولی سازگار پاسخ می‌دهد؛ فرض می‌شود که اوراکل در دسترس همه طرف‌ها، از جمله حمله‌کننده قرار دارد، همان‌گونه که تابع درهم‌ساز در دسترس همه می‌باشد. چنین اثباتی نشان می‌دهد که مگر در حالتی که حمله‌کننده مسئله دشوار را در قلب کاهش امنیت حل کند، حمله‌کننده باید از خواص جالب توجه تابع درهم‌ساز برای شکستن قرارداد استفاده کند؛ آنها نمی‌توانند با تابع درهم‌ساز به عنوان یک جعبه سیاه برخورد کنند (به عنوان یک اوراکل تصادفی).
هم‌چنین نگاه کنید به
ماشین تورینگ