ماشین اوراکل

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در نظریه‌ی پیچیدگی و نظریه‌ی محاسبه‌پذیری، ماشین اوراکل (یا ماشین سروش) یک ماشین انتزاعی برای مطالعه‌ی مسائل تصمیم است. می‌توان آن‌را به عنوان ماشین تورینگ همراه با یک جعبه‌ی سیاه ،که به آن اوراکل گفته می‌شود، در نظر گرفت که قادر به تصمیم‌گیریِ مسائل تصمیم خاصّی در یک تک‌اقدام است. مسئله می‌تواند از هر رده‌ی پیچیدگی باشد. حتّی مسائل تصمیم‌ناپذیر، مثلِ مسئله‌ی توقّف، می‌توانند استفاده شوند.

اوراکِل‌ها[ویرایش]

ماشین اوراکل را می‌توان یک ماشین تورینگ متصّل به یک اوراکل تصوّر کرد. اوراکل، در این مبحث، موجودیّتی قادر به حل یک سری مسائل است، که به عنوان مثال می‌تواند مسئله‌ی تصمیم یا مسئله‌ی تابع باشد. مسئله ممکن است محاسبه‌پذیر نباشد؛ اوراکل یک ماشین تورینگ یا برنامه‌ی کامپیوتری تلقّی نمی‌شود. اوراکل به طورِ ساده یک «جعبه‌ی سیاه» است که قادر به تولید پاسخی برای هر نمونه از یک مسئله‌ی محاسباتی است:

  • یک مسئله‌ی تصمیم به صورت مجموعه‌ی A از اعداد طبیعی (یا رشته‌ها) بیان می‌شود. یک نمونه از مسئله یک عدد طبیعی (یا رشته)ی دل‌خواه است. پاسخ به این نمونه در صورتی که عدد (یا رشته) عضو این مجموعه باشد «بله» و در غیر این صورت «نه» می‌باشد.
  • مسئله‌ی تابع به صورت یک تابع f از اعداد طبیعی (یا رشته‌ها) به اعداد طبیعی (یا رشته‌ها) بیان می‌شود. یک نمونه از این مسئله یک ورودی x برای f؛ و پاسخ آن مقدار (f(x است.

یک ماشین اوراکل می‌تواند تمام اعمال معمول یک ماشین تورینگ را به انجام برساند، و هم‌چنین می‌تواند از اوراکل برای به دست آوردن پاسخی برای هر نمونه از مسئله‌ی محاسباتی برای آن اوراکل بهره ببرد. برای مثال اگر مسئله یک مسئله‌ی تصمیم بر روی یک مجموعه‌ی A از اعداد طبیعی باشد، ماشین اوراکل یک عدد طبیعی به اوراکل عرضه می‌دارد، و اوراکل بسته به این که آن عدد عضو 'A' باشد با «بله» یا «نه» پاسخ می‌دهد.

تعاریف[ویرایش]

تعاریف هم‌ارز متعدّدی برای ماشین تورینگ اوراکل وجود دارد، که در پایین در مورد آن‌ها بحث شده است. موردی که این‌جا ارائه شده است از van Melkebeek است (۲۰۰۰:۴۳).

یک ماشین اوراکل مانند یک ماشین تورینگ شامل اجزای زیر است:

  • یک نوار کار: دنباله‌ای از خانه‌ها بدون شروع یا انتها، که هر کدام می‌تواند شامل یک B (برای خانه‌ی خالی) یا یک نماد از الفبای نوار باشد؛
  • یک هِد خواندن/نوشتن، که بر روی یک خانه از نوار کار می‌ایستد و می‌تواند داده‌ی آن را بخواند، داده‌ی جدید بنویسد، و بر روی نوار به راست یا چپ حرکت کند؛
  • یک سازوکار کنترلی، که می‌تواند در یکی از متناهی تعداد حالت‌هایش باشد، و بسته به حالت فعلی و داده‌ی خوانده‌شده اعمال متفاوتی (خواندن داده، نوشتن داده، حرکت سازوکار کنترلی، و تغییر حالت‌ها) را انجام می‌دهد.

علاوه بر این اجزا، یک ماشین اوراکل شامل اجزای زیر نیز هست:

  • یک نوار اوراکل، که نواری نیمه‌نامتناهی جدای از نوار کار است. الفبای نوار اوراکل می‌تواند متفاوت از الفبای نوار کار باشد؛
  • یک هِد اوراکل که، همانند هِد خواندن/نوشتن، می‌تواند روی نوار اوراکل به چپ یا راست حرکت کرده و نمادها را بخواند یا بنویسد؛
  • دو حالت ویژه: حالت پرسش و حالت پاسخ.

گاه‌به‌گاه، ماشین اوراکل ممکن است وارد حالت پرسش شود. هنگام این رخ‌داد، اعمال زیر در یک مرحله‌ی محاسباتی انجام می‌شوند:

  • محتویّات نوار پرس‌وجو به عنوان یک نمونه از مسئله‌ی محاسباتی اوراکل دیده می‌شود؛
  • پس از مشورت با اوراکل، محتویّات نوار پرس‌وجو با پاسخ آن نمونه از مسئله جای‌گزین می‌شود؛
  • هِد اوراکل به اوّلین خانه از نوار اوراکل منتقل می‌شود؛
  • حالت ماشین اوراکل به وضعیّت پاسخ تغییر می‌یابد.

بنابراین تأثیر تغییر به حالت پرسش، گرفتن پاسخ، در یک مرحله، به نمونه‌ای از مسئله است که بر روی نوار اوراکل نوشته شده است.

تعاریف جای‌گزین[ویرایش]

علاوه بر تعریفی که در بالا ارائه شد تعاریف جای‌گزینِ دیگری نیز وجود دارند. تعدادی از آن‌ها خاصِّ موردی هستند که اوراکِل یک مسئله‌ی تصمیم را حل می‌کند. در این مورد:

  • در بعضی تعاریف، به جای نوشتن پاسخ در نوار اوراکِل، دو حالت خاصِّ بله و خیر علاوه بر حالت پرسش وجود دارد. وقتی اوراکِل مورد مشورت قرار می‌گیرد، حالت بله انتخاب می‌شود اگر محتویّات نوار اوراکِل درون مجموعه‌ی اوراکِل باشد، و حالت خیر انتخاب می‌شود اگر محتویّات درون مجموعه‌ی اوراکِل نباشد (Adachi ۱۹۹۰:۱۱۱).
  • بعضی تعاریف از نوار اوراکِل مجزّا خودداری می‌کنند. هنگامی که وارد حالت اوراکِل می‌شویم، یک نماد نوار مشخّص می‌شود. تعداد دفعاتی که این نماد روی نوار کار ظاهر شده‌است از اوراکِل پرسیده‌ می‌شود. اگر آن عدد درون مجموعه‌ی اوراکِل باشد، حالت بعدی حالت بله است؛ در غیر این صورت، حالت بعدی حالت خیر است (Rogers ۱۹۶۷:۱۲۹).
  • تعریف جای‌گزین دیگر نوار اوراکِل را فقط‌خواندنی می‌کند، و حالت‌های پرسش و پاسخ را به طور کلّی حذف می‌کند. قبل از شروع به کار ماشین، تابع مشخّصه‌ی مجموعه‌ی اوراکِل با استفاده از نمادهای ۰ و ۱ روی نوار اوراکِل نوشته می‌شود. پس از آن ماشین قادر است تا با پیدا کردن خانه‌ی مناسب بر روی نوار اوراکِل و خواندن مقدار ازقبل نوشته‌شده در آن، از اوراکل پرس‌وجو کند (Soare ۱۹۸۷:۴۷، Rogers ۱۹۶۷:۱۳۰).

این تعاریف از منظر محاسبه‌پذیری تورینگ معادل هستند: تابعی که تحت اوراکِل یکی از این تعاریف، اوراکِل‌محاسبه‌پذیر باشد، تحت هر دیگری نیز اوراکِل‌محاسبه‌پذیر است. هرچند از منظر پیچیدگی محاسباتی، این تعاریف معادل نیستند. تعریفی مانند آن‌چه که van Melkebeek ارائه داده‌بود، که در آن از نوار اوراکِلی که ممکن است الفبای خود را داشته باشد استفاده می‌شود، در حالت عمومی لازم است.

کلاس‌های پیچیدگی ماشین اوراکِل[ویرایش]

کلاس پیچیدگی مسائل تصمیمِ حل‌پذیر توسّط الگوریتمی در کلاس A با استفاده از اوراکِلی برای زبان AL، L نامیده می‌شود. به طور مثال، PSAT کلاس مسائل حل‌پذیر در زمان چندجمله‌ای توسّط یک ماشین تورینگ قطعی با اوراکلی برای مسئله‌ی ارضاپذیری بولی (SAT) است. نمادگذاری AB را می‌توان برای مجموعه‌ی زبان‌های B (یا کلاس پیچیدگی B)، با استفاده از تعریف زیر، تعمیم داد:

A^B = \bigcup_{L \in B} A^L

زمانی که یک زبانِ L برای کلاس B کامل باشد، آن‌گاه AL=AB در صورتی که ماشین‌های درون A بتوانند تقلیل‌های استفاده‌شده در تعریف کامل بودن کلاس B را اجرا نمایند. به طور خاص، از آن‌جایی که مسئله‌ی ارضاپذیریِ بولی نسبت به تقلیل‌های زمان چندجمله‌ای ان‌پی کامل است، PSAT=PNP. هرچند، اگر A=DLOGTIME (کلاس مسائل حل‌پذیر در زمان لگاریتمی توسّط ماشین تورینگ قطعی)، آن‌گاه ASAT ممکن است برابر با ANP نباشد.

واضح است که NP ⊆ PNP، ولی این پرسش که آیا NP، PNP، NPNP و P برابر هستند یا نه، در بهترین حالت عملی باقی می‌مانند. باور بر تفاوت آن‌هاست و این باعث تعریف سلسله‌مراتب چند‌جمله‌ای می‌شود.

ماشین‌های اوراکل، با در نظر گرفتن رابطه‌ی بین PA و NPA برای یک اوراکل A، برای بررسی رابطه‌ی بین کلاس‌های پیچیدگی P و NP مفید هستند. به طور خاص، نشان داده شده است که وجود دارند زبان‌های A و B، به قسمی که PA=NPA و (Gill PB≠NPB، Baker و Solovay 1975). این حقیقت که پرسش P = NP از هر دو جهت به صورت نسبی است، به این دلیل است که پاسخ به این پرسش دشوار است، زیرا تکنیک اثباتی که به صورت نسبی انجام می‌گیرد (بدون تاثیر گرفتن از اضافه شدن یک اوراکل) نمی‌تواند به پرسش P = NP پاسخ دهد. بسیاری از تکنیک‌های اثبات از نسبی سازی استفاده می‌کنند.

در نظر گرفتن حالتی که یک اوراکل از میان تمام اوراکل‌های ممکن(یک مجموعه بینهایت) به صورت تصادفی انتخاب شود، قابل توجه است. در این حالت نشان داده شده است که با احتمال یک، PA≠NPA (Bennet و Gill 1981). هنگامی که پاسخ سوالی برای همه‌ی اوراکل‌ها درست باشد، در آن صورت پاسخ پرسش برای یک اوراکل تصادفی نیز درست است. این انتخاب اصطلاحات با دانستن این حقیقت که اوراکل‌های تصادفی یک عبارت را فقط با احتمال 1 یا 0 تایید می‌کنند، قابل توجیه است. (این از روی قانون یک‌صفر Kolmogorov بدست می‌آید.) به عنوان یک گواه P≠NP. یک عبارت ممکن است همزمان برای یک اوراکل تصادفی درست و برای یک ماشین تورینگ عادی غلط باشد؛ برای مثال برای اوراکل‌های A، IPA≠PSPACEA، در حالی که IP = PSPACE (Chang et al، 1994).

اوراکِل‌ها و مسئله‌ی پایان‌پذیری[ویرایش]

ممکن است که وجود اوراکلی را فرض کرد که قادر به محاسبه‌ی یک تابع محاسبه‌ناپذیر باشد، مانند پاسخ به مسئله‌ی توقّف یا مسائل مشابه دیگر. ماشینی با چنین اوراکلی یک فراکامپیوتر است.

به طرز جالبی، پارادوکس پایان‌پذیری هنوز در مورد این ماشین‌ها نیز صدق می‌کند؛ با وجود اینکه این ماشین‌ها می‌توانند تعیین کنند که آیا ماشین تورینگ خاصی با ورودی‌های خاصی به حالت پایان خواهد رسید، به طور کلی، آنها نمی‌توانند تعیین کنند که آیا ماشین‌های معادل خودشان به حالت پایان خواهند رسید. این حقیقت منجر به ایجاد سلسله مراتبی از ماشین‌ها به نام سلسله مراتب محاسباتی می‌شود، که هر رده دارای اوراکل پایان‌پذیری قوی‌تر و مسئله‌ی پایان‌پذیری قوی‌تری است.

کاربردها در رمزنگاری[ویرایش]

در رمزنگاری، اوراکل‌ها برای استدلال در مورد امنیت قراردادهای رمزنگاری که در آنها یک تابع درهم‌ساز استفاده شده است، به کار می‌رود. یک کاهش امنیت برای یک قرارداد در حالتی داده می‌شود که، به جای یک تابع درهم‌ساز، یک اوراکل تصادفی به هر درخواست به صورت تصادفی ولی سازگار پاسخ می‌دهد؛ فرض می‌شود که اوراکل در دسترس همه‌ی طرف‌ها، از جمله حمله‌کننده قرار دارد، همان‌گونه که تابع درهم‌ساز در دسترس همه می‌باشد. چنین اثباتی نشان می‌دهد که مگر در حالتی که حمله‌کننده مسئله‌ی دشوار را در قلب کاهش امنیت حل کند، حمله‌کننده باید از خواص جالب توجه تابع درهم‌ساز برای شکستن قرارداد استفاده کند؛ آنها نمی‌توانند با تابع درهم‌ساز به عنوان یک جعبه‌ی سیاه برخورد کنند (به عنوان یک اوراکل تصادفی).

هم‌چنین نگاه کنید به[ویرایش]

منابع[ویرایش]

صفحه‌ی ماشین اوراکِل در ویکی‌پدیایِ انگلیسی