ランダム化計算と対話型計算

アルゴリズムがコインを投げたり、強力だが信頼できない証明者と対話したりすることを可能にすると、BPPやIPのような複雑性クラスが生まれ、効率的な検証が達成できることについての我々の理解を再構築します。

Definition

ランダム化計算は、ランダムなビットへのアクセスを機械に付与し、正しい答えが得られる確率を測定します。一方、対話型計算は、多項式時間検証者が証明者とメッセージを交換することを可能にします。結果として得られるクラスは、限定された誤差で解決できる問題や、対話を通じて検証できる問題を捉えます。

Scope

このトピックでは、BPP、RP、ZPPを含む確率的複雑性クラスと、ランダム性を排除できるかどうかの問題、対話型証明システムとIPをPSPACEと同一視する定理、ゼロ知識証明、および近似の困難さの根底にある確率的に検証可能な証明について扱います。

Core questions

• ランダム性へのアクセスは、アルゴリズムがより多くの問題を効率的に解決することを可能にするでしょうか？
• 限られた検証者は、信頼できない強力な証明者による主張を検証できるでしょうか？
• ある主張が真実であることを、それ以外の何も知ることなく確信するにはどうすればよいでしょうか？
• 対話型および確率的証明検証は近似をどのように制約するでしょうか？

Key theories

IP = PSPACE

多項式時間検証者と全能の証明者との間の対話型プロトコルによって証明可能な言語は、多項式空間で決定可能な言語と正確に一致します。これは対話の力の驚くべき尺度です。

PCP定理

NP内のすべての問題は、ランダムに選択された定数個のビットのみを読み取ることで検証できる証明を持ちます。この結果は、多くの最適化問題の近似がNP困難となる正確な閾値を特定します。

Clinical relevance

これらのアイデアは直接的な技術的影響を及ぼします。ゼロ知識証明は認証とプライバシー保護プロトコルを可能にし、ブロックチェーンにおける検証可能な計算の基盤となります。一方、確率的に検証可能な証明は、多くの最適化問題が効率的に近似できない理由を説明し、近似アルゴリズムが成功できる場所とできない場所を導きます。

History

対話型証明とゼロ知識証明は、1980年代半ばにGoldwasser、Micali、Rackoff、およびBabaiによって導入されました。Shamirは1990年にIPがPSPACEに等しいことを証明し、1990年代初頭にAroraらによって完成されたPCP定理は近似の研究に革命をもたらしました。一方、ランダム化多項式時間が決定論的多項式時間に等しいという未解決の予想は依然として残っています。

Debates

ランダム性は真の計算能力を追加するのか？

多くの結果は、もっともらしい困難性仮定の下でBPPがPに等しいことを示唆しており、これは原理的に効率的なアルゴリズムからランダム性を除去できることを意味します。この非ランダム化が無条件に成り立つかどうかは未解決であり、ランダム性が実際にどれほど不可欠であるかという問題が残されています。

Key figures

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

Seminal works

• aroraBarak2009
• goldreich2008

Frequently asked questions

コインを投げることがアルゴリズムにどのように役立つのでしょうか？

ランダム性により、アルゴリズムは敵対者が予測できない選択を行うことで最悪のケースの入力を回避でき、素数判定のように、より単純または高速な手順をもたらすことがよくあります。限定誤差クラスBPPは、このようにして、小さく制御可能なエラーの確率で解決できる問題を捉えます。

ゼロ知識証明とは何ですか？

これは、検証者にある主張が真実であることを、その真実性以外に何も、それがなぜ成り立つのかさえも明らかにすることなく納得させる対話型プロトコルです。このような証明により、例えば、パスワードや秘密を知っていることを開示することなく証明することが可能になり、現代の暗号学的プライバシーの基礎となっています。