آلة أوراكل

في نظرية التعقيد ونظرية الحوسبة ، تُعرَّف آلة أوراكل بأنها آلة مجردة يمكنها الاستعلام من صندوق أسود يُسمى أوراكل ، وهو قادر على تقديم إجابة لأي حالة من حالات مشكلة معينة .${\displaystyle R}$في عملية واحدة. المشكلة${\displaystyle R}$يمكن أن تكون المسألة من أي فئة تعقيد ، أو حتى مسألة غير قابلة للحل مثل مسألة التوقف . إذا كانت هناك مسألة أخرى${\displaystyle R'}$يمكن اختزالهاإلى​​${\displaystyle R}$في وقت متعدد الحدود ، ثم آلة أوراكل (مع${\displaystyle R}$يمكن لـ ( أوراكل) حل${\displaystyle R'}$في وقت متعدد الحدود؛ يمكن القول أن${\displaystyle R'}$⁠ يندرج ضمن فئة التعقيد النسبي ⁠${\displaystyle {\mathsf {P}}^{R}}$. فئات التعقيد النسبي الأخرى مثل${\displaystyle {\mathsf {NP}}^{R}}$ويمكن تعريفها بشكل مماثل. ^{[ 1 ]}

يمكن تصور آلة أوراكل على أنها آلة تورينج متصلة بجهاز أوراكل . في هذا السياق، يُعد جهاز الأوراكل كيانًا قادرًا على حل مشكلة ما، والتي قد تكون على سبيل المثال مشكلة قرار أو مشكلة دالة . لا يشترط أن تكون المشكلة قابلة للحساب؛ ولا يُفترض أن يكون جهاز الأوراكل آلة تورينج أو برنامج حاسوب. جهاز الأوراكل ببساطة هو " صندوق أسود " قادر على إنتاج حل لأي حالة من حالات مشكلة حسابية معينة .

• تُمثَّل مسألة القرار بمجموعة A من الأعداد الطبيعية (أو السلاسل النصية ). وتُمثِّل كل حالة من حالات هذه المسألة عددًا طبيعيًا (أو سلسلة نصية) عشوائيًا. ويكون حل هذه الحالة "نعم" إذا كان العدد (أو السلسلة النصية) موجودًا في المجموعة، و"لا" في غير ذلك.
• تُمثَّل مسألة الدالة بعلاقة ثنائية R تربط الأعداد الطبيعية (أو السلاسل النصية) ببعضها. مثال على هذه المسألة هو المدخل x للعلاقة R. الحل هو قيمة مرتبطة بـ x بواسطة العلاقة R.

تستطيع آلة أوراكل تنفيذ جميع العمليات المعتادة لآلة تورينج، كما يمكنها الاستعلام من الأوراكل للحصول على حل لأي مسألة حسابية تخصها. على سبيل المثال، إذا كانت المسألة مسألة قرار لمجموعة A من الأعداد الطبيعية، فإن آلة أوراكل تزود الأوراكل بعدد طبيعي، فيرد الأوراكل بـ "نعم" أو " لا" موضحًا ما إذا كان هذا العدد عنصرًا من عناصر A.

توجد العديد من التعريفات المكافئة لآلات تورينج أوراكل، كما هو موضح أدناه. التعريف المقدم هنا مأخوذ من فان ميلكبيك (2003 ، ص 43) . 

تتضمن آلة التنبؤ، مثل آلة تورينج، ما يلي:

• شريط العمل : سلسلة من الخلايا بدون بداية أو نهاية، قد تحتوي كل منها على حرف B (للدلالة على الفراغ) أو رمز من أبجدية الشريط؛
• رأس القراءة /الكتابة ، الذي يستقر على خلية واحدة من شريط العمل ويمكنه قراءة البيانات الموجودة هناك، وكتابة بيانات جديدة، وزيادة أو إنقاص موضعه على طول الشريط؛
• آلية تحكم ، يمكن أن تكون في واحدة من عدد محدود من الحالات ، والتي ستنفذ إجراءات مختلفة (قراءة البيانات، وكتابة البيانات، وتحريك رأس القراءة/الكتابة، وتغيير الحالات) اعتمادًا على الحالة الحالية والبيانات التي تتم قراءتها.

بالإضافة إلى هذه المكونات، تتضمن آلة أوراكل أيضًا ما يلي:

• شريط التنبؤ ، وهو شريط شبه لانهائي منفصل عن شريط العمل. قد تختلف الأبجدية المستخدمة في شريط التنبؤ عن الأبجدية المستخدمة في شريط العمل.
• رأس أوراكل ، مثل رأس القراءة/الكتابة، يمكنه التحرك يسارًا أو يمينًا على طول شريط أوراكل لقراءة وكتابة الرموز؛
• حالتان خاصتان: حالة السؤال وحالة الاستجابة.

قد تدخل آلة أوراكل من حين لآخر في حالة ASK. وعند حدوث ذلك، تُنفذ الإجراءات التالية في خطوة حسابية واحدة:

• تُعتبر محتويات شريط أوراكل بمثابة مثال على مشكلة الحساب الخاصة بالأوراكل؛
• يتم استشارة الوسيط، ويتم استبدال محتويات شريط الوسيط بحل تلك الحالة من المشكلة؛
• يتم نقل رأس الأوراكل إلى المربع الأول على شريط الأوراكل؛
• تم تغيير حالة جهاز أوراكل إلى استجابة.

وبالتالي فإن تأثير التغيير إلى حالة ASK هو الحصول، في خطوة واحدة، على حل لحالة المشكلة المكتوبة على شريط أوراكل.

تُسمى فئة تعقيد مسائل القرار التي يمكن حلها بواسطة خوارزمية من الفئة A مع وسيط منطقي للغة L ^{، AL} . على سبيل المثال، P ^SAT هي فئة المسائل التي يمكن حلها في وقت متعدد الحدود بواسطة آلة تورينغ حتمية مع وسيط منطقي لمسألة الإرضاء البولياني . يمكن توسيع الترميز AB ^ليشمل مجموعة من اللغات B (أو فئة تعقيد B )، باستخدام التعريف التالي:

${\displaystyle A^{B}=\bigcup _{L\in B}A^{L}}$

عندما تكون اللغة L كاملةً بالنسبة لفئة B ، فإن A L = A  B بشرط أن تتمكن الآلات في A من تنفيذ عمليات الاختزال المستخدمة في تعريف اكتمال الفئة B. على وجه الخصوص، بما أن SAT هي مسألة NP-كاملة بالنسبة لعمليات الاختزال ذات الوقت متعدد الحدود، فإن P SAT = P NP . ومع ذلك، إذا كانت A = DLOGTIME ، فقد لا تساوي A SAT  A NP . (تعريف${\displaystyle A^{B}}$ما سبق ذكره ليس معيارياً تماماً. في بعض السياقات، مثل إثبات نظريات التسلسل الهرمي للزمان والمكان ، يكون من المفيد أكثر افتراض أن الآلة المجردة التي تُعرّف الفئة${\displaystyle A}$لا يملك سوى إمكانية الوصول إلى وسيط واحد للغة واحدة. في هذا السياق،${\displaystyle A^{B}}$لا يتم تعريفها إذا كانت فئة التعقيد${\displaystyle B}$لا توجد أي مشاكل كاملة فيما يتعلق بالتخفيضات المتاحة لـ${\displaystyle A}$.)

من المعلوم أن NP ⊆ P ^NP ، لكن مسألة تساوي NP ^NP وP ^NP وNP وP تبقى محل نقاش. يُعتقد أنها مختلفة، وهذا ما يُفضي إلى تعريف التسلسل الهرمي لكثيرات الحدود .

تُعدّ آلات أوراكل مفيدةً لدراسة العلاقة بين فئتي التعقيد P وNP ، وذلك من خلال دراسة العلاقة بين P ∩ ^A وNP ∩ ^A بالنسبة لأوراكل A. وقد ثبت، على وجه الخصوص، وجود لغتين A و B بحيث يكون P ^{∩ A} = NP ∩ ^A وP ∩ ^B ≠ NP ∩ ^{B. [ 5 ]} ويُعتبر كون مسألة P = NP نسبية في كلا الاتجاهين دليلاً على صعوبة الإجابة على هذا السؤال، لأن أي أسلوب إثبات نسبي ( أي لا يتأثر بإضافة أوراكل) لن يُجيب على مسألة P = NP. ^{[ 6 ]} ومعظم أساليب الإثبات نسبية. ^{[ 7 ]}

يمكن النظر في حالة اختيار وسيط عشوائيًا من بين جميع الوسائط الممكنة ( مجموعة لانهائية ). وقد ثبت في هذه الحالة أنه باحتمالية 1، فإن P ^A ≠ NP ^{A. [ 8} ] عندما يكون سؤال ما صحيحًا بالنسبة لجميع الوسائط تقريبًا، يُقال إنه صحيح بالنسبة لوسيط عشوائي . يُبرر هذا المصطلح بحقيقة أن الوسائط العشوائية تدعم عبارة باحتمالية 0 أو 1 فقط. (يتبع هذا من ^قانون كولموغوروف للصفر والواحد ). هذا دليل ضعيف فقط على أن P ≠ NP، حيث قد تكون العبارة صحيحة بالنسبة لوسيط عشوائي ولكنها خاطئة بالنسبة لآلات تورينغ العادية؛ على سبيل المثال، IP ^A ≠ PSPACE ^A لوسيط عشوائي A ولكن IP = PSPACE . ^{[ 9 ]}

تستطيع الآلة المزودة بخوارزمية أوراكل لحل مشكلة التوقف تحديد ما إذا كانت آلات تورينغ معينة ستتوقف عند مدخلات محددة، لكنها لا تستطيع تحديد ما إذا كانت الآلات المزودة بخوارزمية أوراكل لحل مشكلة التوقف ستتوقف بشكل عام. هذا يُنشئ تسلسلاً هرمياً للآلات، كل منها مزود بخوارزمية أوراكل أقوى لحل مشكلة التوقف ومشكلة توقف أصعب. يمكن استخدام هذا التسلسل الهرمي للآلات لتعريف التسلسل الهرمي الحسابي . ^{[ 10 ]}

في علم التشفير ، تُستخدم مصادر البيانات الموثوقة (أوراكل) لتقديم حجج تدعم أمان بروتوكولات التشفير التي تستخدم دالة تجزئة . ويُقدّم برهان أمني (إثبات أمان) للبروتوكول في حالة استخدام مصدر بيانات موثوق عشوائي، بدلاً من دالة التجزئة، للإجابة على كل استعلام بشكل عشوائي ولكن متسق؛ ويُفترض أن يكون هذا المصدر متاحًا لجميع الأطراف، بما في ذلك المهاجم، كما هو الحال مع دالة التجزئة. يُبيّن هذا البرهان أنه ما لم يتمكن المهاجم من حلّ المشكلة المعقدة التي تكمن وراء هذا البرهان الأمني، فعليه استغلال خاصية مهمة في دالة التجزئة لاختراق البروتوكول؛ إذ لا يمكنه التعامل مع دالة التجزئة كصندوق أسود (أي كمصدر بيانات موثوق عشوائي).