محاسبات تصادفی و تعاملی

اجازه دادن به الگوریتم‌ها برای پرتاب سکه یا درگیر شدن در گفتگو با یک اثبات‌کننده قدرتمند اما غیرقابل اعتماد، منجر به کلاس‌های پیچیدگی مانند BPP و IP می‌شود که درک ما را از آنچه تأیید کارآمد می‌تواند به دست آورد، تغییر می‌دهد.

Definition

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

Scope

این موضوع شامل کلاس‌های پیچیدگی احتمالی از جمله BPP، RP و ZPP و این سؤال است که آیا تصادفی بودن قابل حذف است، سیستم‌های اثبات تعاملی و قضیه‌ای که IP را با PSPACE یکسان می‌داند، اثبات‌های با دانش صفر، و اثبات‌های قابل بررسی احتمالی که زیربنای سختی تقریب هستند.

Core questions

• آیا دسترسی به تصادفی بودن به الگوریتم‌ها اجازه می‌دهد تا مسائل بیشتری را به طور کارآمد حل کنند؟
• آیا یک تأییدکننده محدود می‌تواند ادعاهای یک اثبات‌کننده قدرتمند و غیرقابل اعتماد را بررسی کند؟
• چگونه می‌توان متقاعد شد که یک گزاره صحیح است در حالی که هیچ چیز دیگری یاد نگرفت؟
• چگونه بررسی اثبات تعاملی و احتمالی، تقریب را محدود می‌کند؟

Key theories

IP برابر PSPACE است

زبان‌هایی که توسط یک پروتکل تعاملی بین یک تأییدکننده با زمان چندجمله‌ای و یک اثبات‌کننده همه‌توان قابل اثبات هستند، دقیقاً همان‌هایی هستند که در فضای چندجمله‌ای قابل تصمیم‌گیری هستند، که یک معیار قابل توجه از قدرت تعامل است.

قضیه PCP

هر مسئله در NP دارای اثبات‌هایی است که می‌توانند با خواندن تنها تعداد ثابتی از بیت‌های تصادفی انتخاب شده تأیید شوند، نتیجه‌ای که آستانه دقیق را مشخص می‌کند که فراتر از آن تقریب بسیاری از مسائل بهینه‌سازی NP-سخت است.

Clinical relevance

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

History

اثبات‌های تعاملی و با دانش صفر توسط گلدواسر، میکالی و راکوف و توسط بابایی در اواسط دهه ۱۹۸۰ معرفی شدند. شامیر در سال ۱۹۹۰ ثابت کرد که IP برابر PSPACE است، و قضیه PCP که توسط آرورا و دیگران در اوایل دهه ۱۹۹۰ تکمیل شد، مطالعه تقریب را متحول کرد، در حالی که حدس موجود مبنی بر اینکه زمان چندجمله‌ای تصادفی برابر با زمان چندجمله‌ای قطعی است، همچنان باز است.

Debates

آیا تصادفی بودن قدرت محاسباتی واقعی اضافه می‌کند؟

بسیاری از نتایج نشان می‌دهند که BPP تحت مفروضات سختی معقول برابر P است، به این معنی که تصادفی بودن اصولاً می‌تواند از الگوریتم‌های کارآمد حذف شود. اینکه آیا این عدم تصادفی‌سازی بدون قید و شرط برقرار است یا خیر، نامشخص است و این سؤال را باز می‌گذارد که تصادفی بودن واقعاً چقدر ضروری است.

Key figures

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

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

چگونه پرتاب سکه می‌تواند به یک الگوریتم کمک کند؟

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

اثبات با دانش صفر چیست؟

این یک پروتکل تعاملی است که یک تأییدکننده را متقاعد می‌کند که یک گزاره صحیح است در حالی که هیچ چیز فراتر از حقیقت آن را فاش نمی‌کند، حتی دلیل صحت آن را. چنین اثبات‌هایی، برای مثال، امکان اثبات اینکه شما یک رمز عبور یا راز را می‌دانید بدون افشای آن را فراهم می‌کنند و اساس حریم خصوصی رمزنگاری مدرن هستند.