ヤオの原理

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

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

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

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

入力 に対するアルゴリズムのコスト指標（実行時間など）について考えます。この指標について、ランダム化アルゴリズムとランダム入力に対する期待値を調べます。また、任意の有限集合の決定論的アルゴリズム（たとえば、アルゴリズムを特定の入力サイズに制限することで有限にしたもの）と、これらのアルゴリズムへの有限集合の入力についても考えます。における決定論的動作の確率分布から得られるランダム化アルゴリズムのクラスを で表し、における入力の確率分布のクラスを で表します。すると、ヤオの原理は次のようになります。^[1]${\displaystyle c(A,x)}$${\displaystyle A}$${\displaystyle x}$ ${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {R}}}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {X}}}$

$${\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)].}$$

ここで、は期待値を表す記号であり、はが に従って分布するランダム変数であることを意味します。およびの有限性により、および は確率ベクトルの単体として解釈できます。^[3]そのコンパクトさは、これらの式の最小値と最大値が存在することを意味します。^[4]${\displaystyle \mathbb {E} }$${\displaystyle x\sim D}$${\displaystyle x}$${\displaystyle D}$${\displaystyle {\mathcal {A}}}$${\displaystyle {\mathcal {X}}}$${\displaystyle {\mathcal {D}}}$${\displaystyle {\mathcal {R}}}$

同じ原理のより弱い形式、すなわち等式ではなく不等式は、決定論的アルゴリズムに対する任意のハード入力分布を、すべてのランダム化アルゴリズムのコストに対する下限に変換します。 がハード入力分布の任意の特定の選択であり、 がにおける任意の特定のランダム化アルゴリズムである場合、^[1] つまり、分布に対する可能な限り最高の決定論的パフォーマンスは、最悪の入力に対する 任意のランダム化アルゴリズムのパフォーマンスの下限です。 この Yao の原理の弱いバージョンは、期待値の線形性や、任意の分布に対して であるという原理 によって直接観察することもできます。 および に対する最大化と最小化を回避することにより、このバージョンの Yao の原理は、 またはが有限でない場合にも適用できます。 ^[5]ただし、不等式ではなく等式を使用するバージョンの Yao の原理は、ランダム化アルゴリズムの下限を証明するときにも役立ちます。この等式は、このように下限を証明しても一般性が失われないことを意味します。つまり、実際に最良のランダム化アルゴリズムが何であれ、その複雑さの下限を証明できる入力分布が存在します。^[6]${\displaystyle D\in {\mathcal {D}}}$${\displaystyle R}$${\displaystyle {\mathcal {R}}}$ $${\displaystyle \min_{A\in{\mathcal{A}}}\mathbb{E}_{x\simD}[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}}}$

コストがアルゴリズムの実行時間を表す場合、ヤオの原理は、ハード入力分布における決定論的アルゴリズムの最善の実行時間は、最悪の入力に対するラスベガスアルゴリズムの期待時間の下限を与えると述べています。ここで、ラスベガスアルゴリズムは、実行時間が変化する可能性があるが、結果は常に正しいランダム化アルゴリズムです。^{[7] [8]たとえば、この形式のヤオの原理は、}ゲームツリーの正確な評価に対する特定のモンテカルロ木探索アルゴリズムの最適性を証明するために使用されています。^[8]${\displaystyle c}$

比較に基づくソートおよび選択アルゴリズムの時間計算量は、データ要素のペア間の比較回数を合計時間の代理として研究されることが多い。これらの問題では、任意の固定数の要素に対して、入力は順列として表現でき、決定論的アルゴリズムは決定木として表現できる。これらは、ヤオの原理が要求するように、どちらも有限の数である。対称化の議論は、最も困難な入力分布を特定する。それらはランダム順列であり、すべての順列が等しく起こり得る異なる要素上の分布である。これは、他の分布が最も困難である場合、同じ困難な分布のすべての順列で平均化することは等しく困難であり、ランダム順列の分布を生成するためである。ヤオの原理は、ランダム順列に対する決定論的アルゴリズムによって行われる比較の平均ケース数の下限を、ランダム比較アルゴリズムの最悪ケース分析に拡張する。^[2]${\displaystyle n}$

ヤオが挙げた例は、与えられた値の集合の中で何番目に大きい値を見つけるアルゴリズムの分析、つまり選択問題である。^[2]ヤオの研究に続いて、ウォルター・クントとイアン・マンローは、ランダムな順列に対して、決定論的アルゴリズムは少なくとも期待される比較を実行しなければならないことを示した。^[9]ヤオの原理によれば、ランダム化されたアルゴリズムは、最悪のケースの入力に対して同じ数の比較を行わなければならない。^[10]フロイド・リベストアルゴリズムは、この境界内で比較を行っている。^[11]${\displaystyle k}$${\displaystyle n}$${\displaystyle n+\min(k,nk)-O(1)}$${\displaystyle O({\sqrt {n\log n}})}$

ヤオによる原理のもう一つのオリジナルな応用は、グラフ特性の回避性、つまりグラフに特定の特性があるかどうかを判断するために必要な頂点のペアの隣接性のテストの回数で、グラフにアクセスする唯一の方法がそのようなテストである場合である。^[2] リチャード・M・カープは、すべての非自明な単調グラフ特性（その特性を持つグラフのすべてのサブグラフに対して真である特性）に対して、ランダム化アルゴリズムは2乗個のテストを必要とするが、より弱い境界しか証明されていないと推測した。^[12]

ヤオが述べたように、空グラフでは真だが、頂点上の辺の数が限られている他のグラフでは偽であるグラフ特性については、ランダム化アルゴリズムは頂点の対の平方数を調査する必要がある。たとえば、9 辺のユーティリティ グラフは非平面であるため、平面グラフという特性については となる。より正確には、ヤオは、これらの特性について、ランダム化アルゴリズムが間違いを犯す確率が最大でも となるように、すべての に対して少なくとも 回のテストが必要であると述べている。また、ヤオはこの方法を使用して、十分に小さい定数のエラー確率に対して、特定のツリーまたはクリークをサブグラフとして含む特性、完全マッチングを含む特性、およびハミルトン閉路を含む特性について、平方数のクエリが必要であることも示した。^[2]${\displaystyle n}$${\displaystyle s}$${\displaystyle s=9}$${\displaystyle \left({\tfrac {1}{2}}-p\right){\tfrac {1}{s}}{\tbinom {n}{2}}}$${\displaystyle \epsilon >0}$${\displaystyle p}$

ブラックボックス最適化では、与えられた関数のクラスから、ある有限領域からの引数による関数の呼び出しを通じてのみアクセスできる関数の最小値または最大値を決定することが問題となる。この場合、最適化されるコストは呼び出し回数である。ヤオの原理は、「選択された問題クラスに対するすべてのランダム探索ヒューリスティックの下限を証明するために利用できる唯一の方法」と説明されている。^[13]この方法で証明できる結果には、次のものがある。

• ビットのバイナリ文字列に対して、入力が固定された未知の文字列と等しいかどうかをテストするブール関数の場合、未知の文字列を見つけるために必要な関数呼び出しの最適な期待回数は です。これは、文字列をランダムな順序でテストする関数によって実現でき、このクラスから一様ランダム関数を選択する入力分布に対してヤオの原理を使用することで最適であることが証明されています。^[13]${\displaystyle n}$${\displaystyle 2^{n-1}+{\tfrac {1}{2}}}$
• ビットのバイナリ文字列から実数への単峰性関数 は、次の特性によって定義されます。各入力文字列 に対して、 はの一意の最大値であるか、または1 ビットでより大きな値を持つ文字列に変更することができます。したがって、 1 ビットずつ変更してより大きな値を生成するローカル検索では、最終的には必ず最大値が見つかります。このような検索には指数関数的に多くのステップが必要になる場合がありますが、大幅に改善することは不可能です。クエリを実行するランダム化アルゴリズムでは、このクラスの関数によって、アルゴリズムが最大値を見つける確率が指数関数的に小さくなります。^[13]${\displaystyle f}$${\displaystyle n}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle f}$${\displaystyle x}$${\displaystyle y}$${\displaystyle 2^{o(n)}}$

通信複雑性では、アルゴリズムは2つ以上の当事者間の通信プロトコルを記述し、そのコストは当事者間で送信されるビット数またはメッセージ数である可能性があります。この場合、ヤオの原理は、問題の最悪のケースである入力分布での決定論的通信プロトコルの平均ケースの複雑さと、最悪のケースの入力でのランダム化プロトコルの予想される通信複雑性との間の等式を記述します。^{[6] [14]}

Avi Wigdersonが説明した例(Manu Viola の論文に基づく) は、それぞれがビットの入力値を持つ 2 つのパーティが、どちらの値が大きいかを判断するための通信の複雑さです。決定論的な通信プロトコルの場合、ビット通信よりも優れたものはありません。これは、一方のパーティが入力全体をもう一方のパーティに送信するだけで簡単に実現できます。ただし、ランダム性のソースを共有し、エラー確率が固定されているパーティは、入力のプレフィックスの1 ビットハッシュ関数を交換して、入力が異なる最初の位置のノイズバイナリ検索を実行し、ビット通信を実現できます。これは、最初の違いの位置を一様にランダムに選択し、その後、その位置までの共有プレフィックスと、その位置以降の残りの入力に対してランダムな文字列を選択する入力分布を持つ Yao の原理によって示されるように、最適値の一定係数内です。^{[6] [15]}${\displaystyle n}$${\displaystyle n}$${\displaystyle O(\log n)}$

ヤオの原理は、オンライン アルゴリズムの競争比率にも適用されています。オンライン アルゴリズムは、将来のリクエストを知らずに、一連のリクエストに応答する必要があり、選択に応じてリクエストごとにいくらかのコストまたは利益が発生します。競争比率とは、そのコストまたは利益と、将来のすべてのリクエストに関する情報にアクセスできるオフライン アルゴリズムによって達成できる値との比率であり、この比率が 1 から可能な限り離れる最悪のケースのリクエスト シーケンスについてです。ここでは、アルゴリズムのパフォーマンスを分子に、オフライン アルゴリズムの最適なパフォーマンスを分母にして比率を定式化するように注意する必要があります。そうすることで、コストの尺度が期待値の逆数ではなく期待値として定式化されます。 ^[5]

Borodin & El-Yaniv (2005) が挙げた例は、ページ置換アルゴリズムに関するもので、与えられたパラメータ に対して、ページのキャッシュを使用して、コンピュータ メモリのページに対する要求に応答するものです。要求がキャッシュされたページと一致する場合、コストはかかりません。そうでない場合は、1 つのページ フォールトのコストで、キャッシュされたページの 1 つを要求されたページで置き換える必要があります。このモデルの要求シーケンスの難しい分布は、各要求をページのプールから一様にランダムに選択することによって生成できます。どの決定論的オンライン アルゴリズムでも、要求 回を超えるページ フォールトの予想があります。代わりに、オフライン アルゴリズムでは、要求シーケンスを、ページのみが使用されるフェーズに分割し、フェーズの開始時にフェーズ内で使用されていない 1 つのページを置き換えるフォールトを 1 つだけ発生させることができます。クーポン コレクターの問題の例として、フェーズあたりの期待される要求数は で、 は番目の調和数です。更新理論により、オフライン アルゴリズムではページ フォールトが発生する確率が高いため、この入力分布に対するどの決定論的アルゴリズムの競合比も少なくとも になります。ヤオの原理によれば、アルゴリズムのランダムな選択を知らない敵対者がアルゴリズムにとって最悪のケースとして選択したリクエストシーケンスに対するランダムページ置換アルゴリズムの競争率も下限に達します。 ^[16]${\displaystyle k}$${\displaystyle k}$${\displaystyle k+1}$${\displaystyle {\tfrac {n}{k+1}}}$${\displaystyle n}$${\displaystyle k}$${\displaystyle (k+1)H_{k}}$${\displaystyle H_{k}=1+{\tfrac {1}{2}}+\cdots +{\tfrac {1}{k}}}$${\displaystyle k}$${\displaystyle {\tfrac {n}{(k+1)H_{k}}}+o(n)}$${\displaystyle H_{k}}$${\displaystyle H_{k}}$

スキーレンタル問題に関連する一般的なオンライン問題に対して、セイデンは問題の特定のパラメータに基づいて、最適に難しい入力分布を導出するためのクックブック法を提案した。^[17]

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

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

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

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