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