姚の原則

計算複雑性理論 において、ヤオの原理（ヤオのミニマックス原理またはヤオの補題とも呼ばれる）は、ランダム化アルゴリズムの性能を決定論的（非ランダム）アルゴリズムの性能に関連付けるものである。この原理は、特定のアルゴリズムのクラスと、アルゴリズムの性能の特定の尺度について、次の2つの量が等しいことを述べている。

• ランダムな入力に対して決定論的アルゴリズムが達成できる最適なパフォーマンス（平均ケースの複雑さ）は、可能な限り困難な確率分布を選択し、その分布に対して可能な限りうまく機能するように選択されたアルゴリズムに対して得られる。
• 決定論的入力に対してランダムアルゴリズムが達成できる最適なパフォーマンス（期待される複雑さ）、最悪ケース入力に対して最高のパフォーマンスを発揮するように選択されたアルゴリズム、およびそのアルゴリズムへの最悪ケース入力

ヤオの原理は、決定論的アルゴリズムでは見つけにくい入力の確率分布を見つけ、ランダム化アルゴリズムの最悪ケースのパフォーマンスにも同じ制限があることを推論することで、ランダム化アルゴリズムのパフォーマンスの限界を証明するためによく使用されます。^{[ 1 ]}

この原理は、1977年の論文で最初に提唱したアンドリュー・ヤオにちなんで名付けられました。 ^{[ 2 ]}これは、ゼロサムゲームの理論におけるミニマックス定理や、線形計画の双対性理論と密接に関連しています。

ヤオの原理は、任意の実数値コスト尺度の観点から定式化されている。${\displaystyle c(A,x)}$アルゴリズムの${\displaystyle A}$入力時に${\displaystyle x}$例えば、実行時間など、ランダム化されたアルゴリズムとランダムな入力に対する期待値を研究したい場合。このコスト尺度で使用されるアルゴリズムは有限集合から抽出される。${\displaystyle {\mathcal {A}}}$決定論的アルゴリズムの場合、問題に有限個のアルゴリズムしか持たせないようにする典型的な方法は、入力を単一のサイズに制限することです。入力もまた、有限個の集合から抽出されるべきです。$\displaystyle {\mathcal {X}}}$も同様の方法で有限にすることができる。次に、各確率分布は${\displaystyle {\mathcal {A}}}$これは、まずランダムに選択を行うランダム化アルゴリズムに対応します。${\displaystyle {\mathcal {A}}}$その分布に従って、選択されたアルゴリズムに従います。このようにして、同じ問題に対するランダム化アルゴリズムのクラスは、クラスとしてモデル化できます。$\displaystyle {\mathcal {R}}}$すべての確率分布について${\displaystyle {\mathcal {A}}}$最後に、ヤオの原理の定式化には、入力に関するすべての確率分布のクラスが含まれます。$\displaystyle {\mathcal {X}}}$と表記される${\displaystyle {\mathcal {D}}}$すると、ヤオの原理は次のように述べている。^{[ 1 ]}

$$\displaystyle \max _{D\in {\mathcal {D}}}\min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]=\min _{R\in {\mathcal {R}}}\max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].}$$

ここ、${\displaystyle \mathbb {E} }$は期待値の表記であり、${\displaystyle x\sim D}$つまり${\displaystyle x}$は、以下に従って分布する確率変数です。${\displaystyle D}$式の左辺は、決定論的アルゴリズムによって得られる最適なパフォーマンスを示している。${\displaystyle A}$ランダムな入力に対して${\displaystyle x}$（その平均的なケースの複雑さ）確率分布の場合${\displaystyle D}$可能な限り難しい入力に対して、${\displaystyle A}$最も優れたパフォーマンスを発揮するアルゴリズムである${\displaystyle D}$右辺は、ランダムアルゴリズムによって得られる最適なパフォーマンスを示しています。${\displaystyle R}$決定論的な入力に対して${\displaystyle x}$（その予想される複雑さ）${\displaystyle R}$最悪の入力ケースで最高のパフォーマンスを発揮し、${\displaystyle x}$は最悪の場合の入力です${\displaystyle R}$[ ^{1 ]有限}性${\displaystyle {\mathcal {A}}}$そして$\displaystyle {\mathcal {X}}}$許可する${\displaystyle {\mathcal {D}}}$そして$\displaystyle {\mathcal {R}}}$確率ベクトルの単体として解釈されるべきであり、^{[ 3 ]}そのコンパクト性は、これらの式における最小値と最大値が存在することを意味する。^{[ 4 ]}

ヤオの原理の別のバージョンでは、等式から不等式へと弱められているが、同時にアルゴリズムと入力が有限集合から得られるという要件を緩和することで一般化されている。不等式の方向により、特定の入力分布が決定論的アルゴリズムにとって困難であることが示されている場合に使用でき、すべてのランダム化アルゴリズムのコストの下限に変換される。このバージョンでは、すべての入力分布に対して、${\displaystyle D\in {\mathcal {D}}}$、そしてすべてのランダム化アルゴリズムについて${\displaystyle R}$で$\displaystyle {\mathcal {R}}}$[ ^{1 ]​}$$\displaystyle \min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)].}$$ つまり、分布に対する最良の決定論的パフォーマンス${\displaystyle D}$は、各ランダム化アルゴリズムのパフォーマンスの下限値です。${\displaystyle R}$最悪の入力値に対して。このバージョンのヤオの原理は、不等式の連鎖によって証明できる。 $${\displaystyle \min _{A\in {\mathcal {A}}}\mathbb {E} _{x\sim D}[c(A,x)]\leq \mathbb {E} _{x\sim D}[c(R,x)]\leq \max _{x\in {\mathcal {X}}}\mathbb {E} [c(R,x)],}$$ それぞれは期待値の線形性と原理のみを使用して示すことができる。${\displaystyle \min \leq \mathbb {E} \leq \max }$すべての分布に対して。最大化と最小化を避けることで${\displaystyle {\mathcal {D}}}$そして$\displaystyle {\mathcal {R}}}$ヤオの原理のこのバージョンは、次のような場合に適用できます。$\displaystyle {\mathcal {X}}}$または${\displaystyle {\mathcal {A}}}$有限ではない。^{[ 5 ]}この不等式の方向はランダム化アルゴリズムの下限を証明するために必要な方向であるが、ヤオの原理の等式バージョンが利用可能な場合は、これらの証明にも役立つ。原理の等式は、下限を証明するために原理を使用しても一般性が失われないことを意味する。実際の最良のランダム化アルゴリズムが何であれ、その複雑さの一致する下限を証明できる入力分布が存在する。^{[ 6 ]}

ヤオの原理は、ゲーム理論の観点から、2人ゼロサムゲームとして解釈できる。このゲームでは、一方のプレイヤーであるアリスが決定論的アルゴリズムを選択し、もう一方のプレイヤーであるボブが入力値を選択する。ペイオフは、選択された入力値に対する選択されたアルゴリズムのコストである。任意のランダム化アルゴリズム${\displaystyle R}$これは、決定論的アルゴリズムの中からランダムに選択されたものと解釈でき、したがってアリスの混合戦略とみなすことができる。同様に、非ランダムなアルゴリズムは、アリスの純粋戦略とみなすことができる。任意の2人ゼロサムゲームにおいて、一方のプレイヤーが混合戦略を選択した場合、もう一方のプレイヤーはそれに対して最適な純粋戦略を持っている。ジョン・フォン・ノイマンのミニマックス定理により、ゲーム値が存在する。${\displaystyle c}$、各プレイヤーの混合戦略により、プレイヤーは期待値を保証できる。${\displaystyle c}$あるいは、それらの戦略を実行することでより良い結果が得られ、混合戦略に対する最適な純粋戦略が期待値を正確に生み出す${\displaystyle c}$したがって、アリスのミニマックス混合戦略は、ボブの最良の純粋戦略と対比して、同じ期待ゲーム値を生み出す。${\displaystyle c}$ボブのミニマックス混合戦略とアリスの最良の対抗純粋戦略とを対比させる。上記のゲームにおける期待ゲーム値のこの等価性は、等式の形をとったヤオの原理である。^{[ 5 ]}ヤオの原理を最初に定式化したヤオの1977年の論文は、このようにしてそれを証明した。^{[ 2 ]}

アリスの最適な混合戦略（ランダム化アルゴリズム）とボブの最適な混合戦略（ハード入力分布）はそれぞれ、一方のプレイヤーの確率を変数とし、もう一方のプレイヤーの選択ごとにゲーム値に制約を設けた線形計画法を用いて計算できます。このようにして各プレイヤーについて得られる 2 つの線形計画法は双対線形計画法であり、その等式は線形計画法の双対性の例です。^{[ 3 ]}ただし、線形計画法は多項式時間で解くことができますが、これらの線形計画法の変数と制約の数（可能なアルゴリズムと入力の数）は通常、明示的に列挙するには大きすぎます。したがって、これらの最適な戦略を見つけるためにこれらの計画法を定式化して解くことは、多くの場合非現実的です。^{[ 13 ] [ 14 ]}

モンテカルロ法は、計算リソースを一定量使用するものの、誤った結果を生成する可能性のあるアルゴリズムですが、ヤオの原理の一種が、アルゴリズムのエラー確率、つまりエラー率に適用されます。可能な限り最も難しい入力分布を選択し、その分布に対して最も低いエラー率を達成するアルゴリズムを選択すると、最適なアルゴリズムとその最悪の場合の入力分布を選択した場合と同じエラー率になります。ただし、このようにして見つかった難しい入力分布は、この原理を適用する際に使用するパラメータの変更に対して頑健ではありません。入力分布が特定のエラー率を達成するために高い複雑性を必要とする場合でも、別のエラー率に対しては予想外に低い複雑性を持つ可能性があります。ベン・デイビッドとブレイスは、多くの自然な計算複雑性尺度の下でのブール関数に対して、すべてのエラー率に対して同時に難しい入力分布が存在することを示しています。^{[ 18 ]}

ヤオの原理の変形も量子コンピューティングで検討されている。ランダム化アルゴリズムの代わりに、あらゆる入力に対して正しい値を計算する確率が高い量子アルゴリズム（少なくとも確率は）を検討することができる。${\displaystyle {\tfrac {2}{3}}}$この条件と多項式時間によって、複雑性クラスBQPが定義されます。決定論的な量子アルゴリズムを求めるのは意味がありませんが、代わりに、与えられた入力分布に対して、正しい答えを計算する確率が 1 であるアルゴリズムを考えることができます。これは、この条件を満たす入力の確率が 1 であるという意味で、弱い意味で正しい答えを計算するアルゴリズムです。${\displaystyle \geq {\tfrac {2}{3}}}$あるいは、さらに、アルゴリズムが残りの入力に対して特定の答えを生成する確率が 0 または 1 でなければならないという強い意味で。任意のブール関数に対して、確率で正しい量子アルゴリズムの最小複雑度${\displaystyle \geq {\tfrac {2}{3}}}$最悪の場合の入力に対する計算量は、難しい入力分布に対して、その分布に対する最良の弱量子アルゴリズムまたは強量子アルゴリズムによって達成できる最小の計算量以下である。この不等式の弱形式は定数倍の範囲内で等式になるが、強形式は等式にならない。^{[ 19 ]}