♥ きちんとした定義 (HC SVNT DRACONES)

複雑性クラス P, NP, co-CP をきちんと定義するには、言語 (language) と Turing 機械を使った議論が必要です。言語とは有限アルファベット \(\Sigma\) 上の文字列の集合であり、\(\Sigma = \lbrace {\color{maroon}{0}}, {\color{maroon}{1}} \rbrace\) と仮定しても一般性は失われません。Turing 機械とは機能が極端に制限されたコンピューターであり、その詳細な定義は計算能力を考えるときには驚くほど重要ではありません。

P は決定性単一テープ Turing 機械を使って多項式時間 (polynomial time) で判定できる言語の集合として定義されます。同様に NP は非決定性 Turing 機械を使って多項式時間で判定できる言語の集合として定義されます。NP は Nondeterminitic Plynomial-time (非決定性多項式時間) の略です。

多項式時間という条件は十分大雑把なので、Turing 機械の正確な形式はどんなものであっても構いません (テープの数、ヘッドの数、トラックの数、アルファベットの数などが違っていても問題ありません)。実際、ランダムアクセス機械1において \(T(n)\) 時間で実行される任意のアルゴリズムは、単一テープ、単一トラック、単一ヘッド の Turing 機械を使って \(O(T(n)^{4})\) 時間でシミュレートできます。このシミュレーションが存在するおかげで、私たちが普段使うような for ループや再帰と言った高レベルなプログラミングの構文を使っても計算複雑性をきちんと議論できます。Turing 機械の言葉を直接使ってアルゴリズムを説明する必要はありません。

正確な定義において問題 \(\Pi\) が NP 困難であるとは、全ての問題 \(\Pi^{\prime} \in \text{NP}\) について \(\Pi^{\prime}\) から \(\Pi\) への多項式時間 Turing 帰着 (Turing reduction) が存在することとして定義されます。ここで Turing 帰着とは、Turing 機械で実行できる帰着のことです: つまり、\(\Pi\) を解く Turing 機械 \(M^{\prime}\) をブラックボックスなサブルーチンとして使って \(\Pi^{\prime}\) を解く Turing 機械 \(M\) のことです。Turing 帰着は神託帰着 (oracle reduction) とも呼ばれ、多項式時間 Turing 帰着は特に Cook 帰着と呼ばれます。

複雑性理論の研究者が NP 困難性を定義するときには多対一帰着 (many-one reduction) を使うことが多いです (多対一帰着は Karp 帰着とも呼ばれます)。ある言語 \(L^{\prime} \subseteq \Sigma^{\ast}\) から別の言語 \(L \subseteq \Sigma^{\ast}\) への多対一帰着とは、関数 \(f: \Sigma^{\ast} \rightarrow \Sigma^{\ast}\) であって \(x \in L^{\prime}\) \(\iff\) \(f(x) \in L\) となるものを言います。多対一帰着を使った場合、言語 \(L\) が NP 困難であることは、任意の言語 \(L^{\prime} \in \text{NP}\) 対して \(L^{\prime}\) から \(L\) への多項式時間で計算できる多対一帰着が存在することとして定義されます。

任意の Karp 帰着は Cook 帰着にできます。つまりある判定問題 \(\Pi\) から別の判定問題 \(\Pi^{\prime}\) への Karp 帰着が存在する場合には、その帰着を使って \(\Pi\) への入力を \(\Pi^{\prime}\) への入力に変換し、\(\Pi^{\prime}\) のオラクル (サブルーチン) を起動してその結果を返すという Cook 帰着が作れるということです。しかし現在分かっている限りでは全ての Cook 帰着が Karp 帰着でシミュレートできるわけではないので、逆は成り立ちません。

複雑性理論の研究者が Karp 帰着を好む主な理由は、 NP が Karp 帰着について閉じているのに対して Cook 帰着については閉じていないためです (NP=co-NP ならば Cook 帰着についても閉じますが、そうではないと考えられています)。(1) Cook 帰着を使った場合には NP 困難だが、(2) Karp 帰着を使った場合には P=NP のときに限って NP 困難となる、という二つの条件を満たす自然な問題が存在します。\(\textsc{UnSAT}\): 「与えられた論理式は常に偽か?」が明らかな例です。

また多対一帰着は判定問題 (正確に言うと判定 “言語” ) だけに対して定義されます。そのため厳密に言えば、Karp-NP 困難な最適化問題あるいは構成問題というものは存在しません。

さらに紛らわしいことに、Cook と Karp は両者とも NP 困難性を対数空間 (logarithmic-space) 帰着を使って定義していました。任意の対数空間帰着は多項式時間帰着ですが、(現在分かっている限り) 逆は成り立ちません。Cook 帰着と Karp 帰着の定義を対数空間帰着から多項式時間帰着に緩和したときに NP 困難な問題の集合が変化するのかどうかは未解決の問題です。

幸運にも、実際の問題においてこれまで述べてきた細かいことが頭をもたげることはありません。特にこの本で紹介される全ての帰着アルゴリズムは対数空間の多対一帰着にできます。ですから、ほら、もう目を覚ましてください。


  1. ランダムアクセス機械 (random access machine, RAM) は物理的なコンピューターで行われる計算のより正確なモデルです。標準的なランダムアクセス機械は無限の配列 \(M[0..\infty]\) を持ち、\(M[i]\) には \(w\) ビットの整数が保持されます (\(w\) は固定された整数)。また任意のメモリアドレスに対する読み込みと書き込みは定数時間で行えます。正式な RAM アルゴリズムはアセンブリの言語を使って書かれ、\(\texttt{ADD } i,j,k\) (\(M[i] \leftarrow\) \(M[j] + M[k]\)) や \(\texttt{INDIR } i,j\) (\(M[i] \leftarrow \) \(M[M[j]]\)) や \(\texttt{IF0GOTO } i,l\) (もし \(M[i] = 0\) なら \(l\) 行に移動せよ) などの命令を持ちます。正確な命令セットは計算能力と驚くほど関係がありません。また全ての命令は単位時間で実行できると定義されます。算術演算の精度にさえ気を付ければ、RAM アルゴリズムは高レベルな疑似コードを使っても正確に書くことができます。[return]