الحوسبة العشوائية والتفاعلية

إن السماح للخوارزميات بقلب العملات المعدنية أو بالانخراط في حوار مع مدقق قوي ولكن غير موثوق به ينتج عنه فئات تعقيد مثل BPP و IP التي تعيد تشكيل فهمنا لما يمكن أن يحققه التحقق الفعال.

Definition

تزيد الحوسبة العشوائية من قدرة الآلة على الوصول إلى البتات العشوائية وتقيس احتمالية الإجابة الصحيحة، بينما تسمح الحوسبة التفاعلية لمدقق بوقت متعدد الحدود بتبادل الرسائل مع مدقق؛ وتلتقط الفئات الناتجة المشكلات القابلة للحل بخطأ محدود أو القابلة للتحقق من خلال التفاعل.

Scope

يغطي هذا الموضوع فئات التعقيد الاحتمالية بما في ذلك BPP و RP و ZPP، ومسألة ما إذا كان يمكن التخلص من العشوائية، وأنظمة الإثبات التفاعلية والنظرية التي تحدد IP مع PSPACE، وإثباتات المعرفة الصفرية، والإثباتات التي يمكن التحقق منها احتماليًا والتي تكمن وراء صعوبة التقريب.

Core questions

• هل يتيح الوصول إلى العشوائية للخوارزميات حل المزيد من المشكلات بكفاءة؟
• هل يمكن لمدقق محدود التحقق من الادعاءات التي يقدمها مدقق قوي غير موثوق به؟
• كيف يمكن للمرء أن يقتنع بأن بيانًا صحيح دون معرفة أي شيء آخر؟
• كيف يحد التحقق التفاعلي والاحتمالي من التقريب؟

Key theories

IP يساوي PSPACE

اللغات التي يمكن إثباتها بواسطة بروتوكول تفاعلي بين مدقق بوقت متعدد الحدود ومدقق كلي القدرة هي بالضبط تلك التي يمكن تحديدها في مساحة متعددة الحدود، وهو مقياس مذهل لقوة التفاعل.

نظرية PCP

كل مشكلة في NP لديها إثباتات يمكن التحقق منها بقراءة عدد ثابت فقط من البتات المختارة عشوائيًا، وهي نتيجة تحدد العتبة الدقيقة التي يتجاوزها تقريب العديد من مشكلات التحسين ليكون NP-hard.

Clinical relevance

لهذه الأفكار تأثير تكنولوجي مباشر: فإثباتات المعرفة الصفرية تمكن من المصادقة وبروتوكولات الحفاظ على الخصوصية وتدعم الحوسبة القابلة للتحقق في سلاسل الكتل (blockchains)، بينما تشرح إثباتات التحقق الاحتمالي سبب عدم إمكانية تقريب العديد من مشكلات التحسين بكفاءة، مما يوجه إلى أين يمكن لخوارزميات التقريب أن تنجح وأين لا يمكنها ذلك.

History

تم تقديم الإثباتات التفاعلية وإثباتات المعرفة الصفرية بواسطة غولدفاسر وميكالي وراكوف وباباي في منتصف الثمانينيات. أثبت شامير أن IP يساوي PSPACE في عام 1990، وأحدثت نظرية PCP، التي أكملها أرورا وآخرون في أوائل التسعينيات، ثورة في دراسة التقريب، بينما لا يزال التخمين القائم بأن الوقت متعدد الحدود العشوائي يساوي الوقت متعدد الحدود الحتمي مفتوحًا.

Debates

هل تضيف العشوائية قوة حاسوبية حقيقية؟

تشير العديد من النتائج إلى أن BPP يساوي P في ظل افتراضات صعوبة معقولة، مما يعني أن العشوائية يمكن من حيث المبدأ إزالتها من الخوارزميات الفعالة. ما إذا كانت هذه الإزالة العشوائية صحيحة بشكل غير مشروط لا يزال غير محسوم، مما يترك الباب مفتوحًا أمام مدى أهمية العشوائية حقًا.

Key figures

• Shafi Goldwasser
• Silvio Micali
• László Babai
• Adi Shamir

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

كيف يمكن لقلب العملات المعدنية أن يساعد الخوارزمية؟

تسمح العشوائية للخوارزمية بتجنب مدخلات أسوأ الحالات عن طريق اتخاذ خيارات لا يمكن للخصم التنبؤ بها، مما يؤدي غالبًا إلى إجراءات أبسط أو أسرع، كما هو الحال في اختبار الأولية. تلتقط فئة الخطأ المحدود BPP المشكلات القابلة للحل بهذه الطريقة مع فرصة صغيرة ومتحكم بها للخطأ.

ما هو إثبات المعرفة الصفرية؟

هو بروتوكول تفاعلي يقنع المدقق بأن بيانًا صحيح دون الكشف عن أي شيء يتجاوز حقيقته، ولا حتى سبب صحته. تسمح هذه الإثباتات، على سبيل المثال، بإثبات أنك تعرف كلمة مرور أو سرًا دون الكشف عنه، وهي أساسية للخصوصية التشفيرية الحديثة.