資源制約尺度

ルッツの資源制約尺度は、複雑性クラスへのルベーグ尺度の一般化である。これはもともとジャック・ルッツによって開発された。ルベーグ尺度がユークリッド空間の部分集合のサイズを定量化する方法を提供するのと同様に、$\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番目の二進文字列（辞書順）が言語に含まれている場合に限り、数列のn番目のビットを 1 に設定するためです。したがって、単位区間内の実数の集合と複雑性クラス（言語の集合）は、どちらも無限二進数列の集合と見なすことができ、実数の集合のサイズを測定するために使用される測度論の手法を複雑性クラスの測定に適用できます。ただし、各計算可能複雑性クラスには可算個の要素しか含まれていないため（計算可能言語の数は可算であるため）、各複雑性クラスのルベーグ測度は 0 です。したがって、複雑性クラス内で測度論を行うには、無限数列の可算集合に対して意味のある代替測度を定義する必要があります。この指標が意味を持つためには、各複雑性クラスの根本的な定義、すなわち、与えられたリソースの範囲内で解決可能な計算問題によって定義されるという点について、何らかの情報を反映する必要がある。

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

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

（これはヴィルのマルチンゲールの原定義であり、後にジョセフ・レオ・ドゥーブによって拡張された。）マルチンゲールdは数列上で成功すると言われている。$${\displaystyle S\in \{0,1\}^{\infty }}$$もし${\displaystyle \limsup _{n\to \infty }d(S\upharpoonright n)=\infty ,}$どこ${\displaystyle S\upharpoonright n}$Sの最初のnビットです。マルチンゲールは一連のシーケンスで成功します。${\displaystyle X\subseteq \{0,1\}^{\infty }}$Xのすべてのシーケンスで成功した場合。

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

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

この種の尺度を複雑性クラスに拡張するために、ルッツはマルチンゲールの計算能力を制限することを検討した。例えば、任意のマルチンゲールを許容する代わりに、マルチンゲールが多項式時間で計算可能であることを要求すれば、p-尺度の定義が得られる。すなわち、ある数列の集合に対して、その集合上で成功する多項式時間で計算可能なマルチンゲールが存在する場合、その集合のp-尺度は0である。また、その集合の補集合のp-尺度が0である場合、その集合のp-尺度は1であると定義する。例えば、NPがp-尺度0を持たないという上記の予想を証明することは、NP全体に対して成功する多項式時間マルチンゲールが存在しないことを証明することに等しい。

ある問題が複雑性クラスCに対してほぼ完全であるとは、その問題が C に属し、かつ C に属する他の「多くの」問題がその問題に帰着する場合をいう。より具体的には、その問題に帰着する C の問題のサブセットが、資源制約尺度に関して尺度 1 の集合である場合である。これは、その問題がクラスに対して完全であるという要件よりも弱い条件である。

• ファン・メルケベーク、ディーター（2001）、『計算複雑性におけるランダム性と完全性』、シュプリンガー、ISBN 3-540-41492-42011年7月19日にオリジナルからアーカイブされました

• 資源制約尺度の参考文献