資源制限のある対策

ルッツの資源限定測度は、ルベーグ測度を複雑性クラスに一般化したものである。これはもともとジャック・ルッツによって開発された。ルベーグ測度がユークリッド空間 の部分集合の大きさを定量化する手法を与えるのと同様に、資源限定測度は複雑性クラスの部分集合の大きさを分類する手法を与える。 ${\displaystyle \mathbb {R} ^{n}}$

例えば、コンピュータ科学者は一般的に、複雑性クラスP (多項式時間で解けるすべての決定問題の集合) は複雑性クラスNP (多項式時間で確認できるが、必ずしも解けるとは限らないすべての決定問題の集合) と等しくないと考えています。 P はNP のサブセットなので、これは NP が P よりも多くの問題を含んでいることを意味します。「P は NP ではない」よりも強い仮説は、「NP は p 測度 0 を持たない」という命題です。ここで、p 測度は、P が含まれる複雑性クラスEのサブセットへのルベーグ測度の一般化です。 P は p 測度 0 を持つことがわかっているので、「NP は p 測度 0 を持たない」という仮説は、NP と P が等しくないだけでなく、NP が測度論的な意味で「P よりもはるかに大きい」ことを意味します。

意味

${\displaystyle \{0,1\}^{\infty }}$ は、すべての無限バイナリシーケンスの集合です。単位区間内の実数は、そのバイナリ展開を考慮することにより、無限バイナリシーケンスと見なすことができます。また、言語(バイナリ文字列の集合) を、シーケンスのn番目のビットを 1 に設定し、その言語にn番目のバイナリ文字列 (辞書式順序) が含まれる場合に限り設定することにより、無限バイナリシーケンスと見なすことができます。したがって、単位区間内の実数集合と複雑性クラス (言語の集合) はどちらも無限バイナリシーケンスの集合と見なすことができ、実数集合のサイズを測定するために使用される測度論の手法を複雑性クラスの測定に適用できます。ただし、各計算可能複雑性クラスには可算数の要素のみが含まれるため (計算可能言語の数が可算であるため)、各複雑性クラスのルベーグ測度は 0 です。したがって、複雑性クラス内で測度論を行うには、無限シーケンスの可算集合で意味のある動作をする別の測度を定義する必要があります。この尺度が意味を持つためには、各複雑性クラスの根本的な定義、つまり、与えられたリソースの制限内で解決できる 計算上の問題によって定義される内容を反映する必要があります。

資源制限測度の基礎は、ヴィルのマルチンゲール定式化である。マルチンゲールとは、すべての有限文字列wに対して、 ${\displaystyle d:\{0,1\}^{*}\to [0,\infty )}$

${\displaystyle d(w)={\frac {d(w0)+d(w1)}{2}}}$ 。

（これはヴィルによるマルチンゲールの元々の定義であり、後にジョセフ・レオ・ドゥーブによって拡張されました。）マルチンゲールdは、Sの最初のnビットが成り立つシーケンスで成功するとされます。マルチンゲールがシーケンスの集合で成功するとは、 Xのすべてのシーケンスで成功することを意味します。 ${\displaystyle S\in \{0,1\}^{\infty}}$ ${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$ ${\displaystyle S\upharpoonright n}$ ${\displaystyle X\subseteq \{0,1\}^{\infty}}$

直感的に言えば、マーチンゲールとは、有限の金額（例えば1ドル）から始めるギャンブラーのようなものです。マーチンゲールは、ビット列を無限に読み取ります。有限のプレフィックスを読み取った後、次のビットが0になる方に現在の資金の一部を賭け、残りの資金を次のビットが1になる方に賭けます。次に現れるビットに賭けた資金は2倍になり、現れなかったビットに賭けた資金は失われます。マーチンゲールは資金のすべてを賭けなければなりませんが、各ビットに資金の半分を賭けることで「何も賭けない」こともできます。マーチンゲールdの場合、d ( w )は文字列wを読み取った後のdの資金を表します。マーチンゲールの定義では、マーチンゲールは何を賭けるかを計算するのではなく、どれだけのお金が残るかを計算することになっていますが、ゲームの制約の性質上、文字列w を見た後にdが0 と 1 に賭けた金額を計算するには、値d ( w )、d ( w0 )、およびd ( w1 )を知っていれば十分です。マーチンゲールは、これまでに見た文字列を入力として受け取る関数であるという事実は、賭けがすでに読み取ったビットの関数のみであることを意味します。他の情報は賭けに影響を与えません (他の情報とは、一般化されたマーチンゲール理論におけるいわゆるフィルタリングです)。 ${\displaystyle \in \{0,1\}^{*}}$

測度とマルチンゲールを関連付ける重要な結果は、ヴィルの観察である。つまり、集合がルベーグ測度0を持つ場合、それはX上で成立するマルチンゲールが存在する場合のみである。したがって、測度0の集合とは、集合のすべての要素上で成立するマルチンゲールが存在する集合と定義できる。 ${\displaystyle X\subseteq \{0,1\}^{\infty}}$

この種の測度を複雑性クラスに拡張するために、ルッツはマルチンゲールの計算能力を制限することを検討した。例えば、任意のマルチンゲールを許容するのではなく、マルチンゲールが多項式時間で計算可能であることを条件とすると、p測度の定義が得られる。すなわち、シーケンスの集合がp測度0を持つとは、その集合上で成立する多項式時間で計算可能なマルチンゲールが存在することを意味する。また、その補集合がp測度0を持つとは、その集合がp測度1を持つことを意味する。例えば、NPはp測度0を持たないという前述の予想を証明することは、NP全体上で成立する多項式時間マルチンゲールが存在しないことを証明することに相当する。

ほぼ完了

ある問題が複雑度クラスCに対してほぼ完全であるとは、その問題がCに含まれ、かつCの他の「多くの」問題がその問題に帰着する場合を言う。より具体的には、その問題に帰着するCの問題の部分集合が、資源制約測度の観点から測度一集合であることを意味する。これは、問題がそのクラスに対して 完全であることよりも弱い要件である。

参考文献

• van Melkebeek, Dieter (2001), 計算複雑性におけるランダム性と完全性, Springer, ISBN 3-540-41492-4、2011年7月19日にオリジナルからアーカイブ

外部リンク

• リソース制限測定法の参考文献