始めに時間限定、領域限定の言語のクラスを定義します。
各クラス C に対して、 co-C は言語の補集合が C に含まれるよ うなクラスを言います。 ある言語 L が決定性のクラス C に含まれる時、 L の補集合の計算は、もと もとの L の決定性の計算をし、出力する値に対して、 yes と no を入れ換え るだけで計算できます。 従って、 Dtime(p(n))=co-Dtime(p(n)), Dspace(p(n))=co-Dspace(p(n)) は明 らかに成り立ちます。
しかし、非決定性の場合、 accept と reject 命令を入 れ換えるだけではうまくいきません。 非決定性の計算では、言語 L に x が含まれるかどうかは x を accept する 計算が存在するかどうかで調べます。 その時、 x を accept する計算が存在しても、 x を reject する計算が存在 しないことは言えません。 従って、 accept と reject を入れ換えた時、次のようになってしまいます。
この場合、あらゆる入力に対して accept してしまうかも知れません。 前に示した、合成数判定問題で accept と reject を交換しても素数判定がで きないことを示します。合成数判定問題を解く非決定性のプログラムに対して、 機械的に accept と reject を交換したものを考えます。
この場合、自分自身と、 1 以外に自分を割り切らない数は n≧3 の時、必ず 存在しますので、この非決定性のプログラムは単に n≧3 を判定するプログラ ムになってしまい、素数を判定することはできません。
このように、非決定性の計算では、クラス C とクラス co-C が等しいかどう かは自明ではありません。 ここでは、ここに示したクラスの関係を調べます。
非決定性では、入力が一つ決まっていても、次の状態が複数あります。 非決定性の Turing 機械に対して、様相を考えると、次の瞬間の様相が複数個 存在します。 但し、 状態やテープに書き込める文 字やテープヘッドの移動がそれぞれ有限の場合しかないので、 1 Step に移ることが可能な様相の数は高々定数個です。 これは一般性を失わず 2 個に制限することができます。 様相を考えると、非決定性の計算は初期状態を根とした木になります (但し、別々の計算から同じ様相に合流することは無視しています)。 これを計算木と言います。 計算木の考え方を使うと、次のことを示すことができます。
p(N) 時間には高々 p(N) 領域しか使えないので明らか
非決定性の Turing 機械が p(N) 時間限定である時、計算木の深さは p(N) に なります。 非決定性に次の状態へ移ることが可能な状態が高々 2 個とすると、木の葉の 数は高々 2p(N) になります。入力が一つ決まれば決定性の計算 で計算木は一つに決定されます。そこで、決定性の計算で初期様相から木の葉を depth-first-search して、全ての木の葉をチェックすることができます。 この時、depth-first-search にかかる時間は木を構成する辺の数の高々定数 倍になります。 従って、 辺の数が 2+4+...+2p(n) = O(2p(N)) になるので、 全ての木の葉を調べ、一つでも accept する計算が存在するかどうかを計算し て yes か no を出力する計算が計算する言語は Dtime(2p(N)) に 含まれます。
領域に関する階層定理と同様に、p(N)領域限定の非決定性の機械の可能な様相 の数も高々 2p(N) になります。 また、使う計算時間も高々 2p(N) になります。 ここで、問題は初期様相から受理様相まで長さ 2p(N) 以内の計 算が存在するか否かを決めることができるかです。 ある様相から別の様相へ t step 以内で移れるかどうかを判定する問題を考え ます。 1 step なら、様相の長さが O(p(N)) なので、実際に移れる様相を全て生成しても O(p(N)) 領域で調べることができます。 いま、出発点と、終点以外に k 個の頂点情報を記憶できる領域があるとしま す。 その時にどれくらいの距離まで調べられるか考えてみましょう。 まず、 1 個だけあった時は単純に出発点と終点の中間に頂点があった時だけ、 つまり距離 2 までしか考えられません。 しかし、 2 個目からは状況が変わります。 単純に考えると、出発点から2 頂点へだてて終点が来る、つまり距離 3 まで しか調べられないような気がします。 しかし、使用した領域は再利用できるため、「2 個目の頂点と出発点まで距離 2 で移れるか?」を調べたあと、「2個目の頂点と終点とが距離 2 で移れるか?」 を考えることができます。すると、これで距離 4 まで調べることができます。 同様に 3 個ある時は、「3 個目の頂点と出発点までが距離 4 で移れるか?」 を調べることができるので、距離 8 まで調べることができます。 結局、 k 個の頂点情報が記憶できる時、距離 2k まで調べること ができます。 最長の計算時間が 2p(N) なら、記憶する頂点情報は高々 p(N) 個 あれば十分なので、様相の長さと必要な個数の積が求める記憶容量になります。 従って、p(N)2 領域あれば、受理様相への計算が存在するかを計 算することができます。
ここでは厳密な証明はせず、証明のアイディアを述べます。 これを示すには、言語 L の補集合を受理する非決定性 p(N) 領域のTuring 機械 M をまず考えます。 言語 L に属する元が入力された時は、全ての計算が reject されます。 逆に L に属さない元が入力された時は、ある計算が accept されます。 このような機械 M の計算木を考えます。
ここで証明のアイディアとしては、もし、 reject される様相の数があらかじ め分かっていれば、非決定性の Turing 機械で p(N) 領域でチェックできると いうことです。 それは次のようにします。 全ての様相に対して、非決定的にチェックするかしないかを決めます。 チェックする時はちゃんと reject するかを確認した上でカウントします。 チェックしない時はカウントしません。 これを全ての様相に対して行い、カウントした数があらかじめ知っている reject される様相の数と等しければ accept します。 このようにすると、入力 x が全ての様相で reject され、さらにあらかじめ 与えられた様相の数が正しい時は、 accept する計算が存在します。
もう一つのアイディアは、t step で移れる様相を非決定的に数え上げられ るということです。 これに関する説明は省略します。
問題の難しさを大雑把に評価することを考えます。 具体的には「実用的な時間で求められる」「実用的な時間では求められない」 など「解ける」「解けない」に直観的に近い感覚を考えます。 そのためにはどんな考え方を導入すればいいでしょうか?
コンピュータプログラムで作成した関数を複数回利用することを考えます。 作成した関数を c(x)、c(x) を計算する時間を t(|x|)、c(x) を計算するのに 必要な領域を s(|x|) とします。 また、別の関数を f(n) とします。
このようにすると、それぞれの計算時間は t(|x|)の定数倍、f(|x|)t(|x|)、t(t'(|x|)) となります。 領域の使用量も単純計算すると同様になります。
t(n),t'(n),f(n) が多項式であるなら、このような定数倍、積、合成に閉じて ますので、結果も多項式になります。 また、指数関数は定数倍、積に対して閉じてます。 一方、単なる c n も定数倍、合成について閉じています。 複数の問題をプログラムで比較するのに、このような関数の性質が あると便利です。 そこで、大雑把な問題の複雑さのクラスとして、直観的な意味を含め次の概念 を導入します。
今までの Turing 機械で定義した問題のクラスと、前節で議論した多項式時間 などの概念を元に、厳密な(かつ大雑把な)問題のクラスを定義します。
これらの関係でわかっているのは次の通りです。
特に、 P が NP と等しいのか異なるのかは計算量理論の中で最大の未解決問 題です。
問題Aの難しさを調べるのに、それを解く有効なプログラムを作ることができ れば、その実行時間により難しさを調べることができます。 しかし、「難しい問題」は一般には有効なプログラムが見つかってません。 そのような問題の難しさを議論するにはどうすれば良いでしょうか?
もし、問題 A を解くために別の問題 B が使えたとします。 例えば、偶数かどうかを判定するのに素因数分解が使えるというような関係を 想定します。 すると、問題 B を解くことができれば、問題 A も解決できるので、問題 A の難易度は高々問題 B 程度であることがわかります。 このように問題を別の問題に変形できるかという概念を reducibilityと言います。 reducibility は推移律(A が B を利用可能で B が C を利用可能なら、A が C を利用可能)を満たすので半順序になります。 従って、reducibility は通常不等号≦で表します。 reducibility のやりかたは多数あります。その中で一番重要なものは、問題 A のインスタンスを yes, no が一致するように問題 B のインスタンスへ対応 づけるもので、インスタンスからインスタンスへ多対一対応(many-one)させる ことから、many-one reducibilityと呼ばれています。 本講義ではインスタンスをその長さの多項式時間で別のインスタンスに変換す る多項式時間 many-one reducibilityだけに絞って話を進めます。 多項式時間 many-one reducibility は通常≦mp と書きます。但し、誤解を招かない限り≦のみを使うことがあります。
半順序では、任意の二つの要素が比較可能かどうかはわかりません。 そこで、どんな要素に対しても小さい要素(最小元)やどんな要素よりも大きい 要素(最大元)が存在するかを調べます。
まず、最小元ですが、問題 A: 「入力が 0 なら no。それ以外は yes」のよう な yes, no のどちらかが有限集合になっているものが考えられます。 その理由は、どんな言語 B を持ってきても、A ≦mp B が成り立つからです。 任意の問題(言語) B を考え、x0 が B に含まれず、 x1 が B に含まれるとします。 すると、「入力が 0 なら x0、 それ以外なら x0」と いう reduction を考えると many-one reducibility になります。
一方、最大元は次のようにすれば各計算のクラスで存在することが分かります。 但し、ここには示しませんでしたが、完全問題が存在しなさそうなクラスもあ ります。
例えばある問題(言語) L が NP に含まれるとします。 すると、定義より L を計算する非決定性の Turing 機械が存在し、入力 x の長さ に対して、その計算時間を制限する多項式 p(|x|) が存在します。 これは、問題を一つ決めると Turing 機械も多項式も一つ決まります。 すると、その Turing 機械のコードを i, p(n)≦ nc+c が常に成り立つよ うな定数を c が得られます。 これにより、任意の入力 x に対して、 (i,x,c) を考えると、CNP を利用して L を解くことができます。 従って、 L ≦ CNP が言えます。
reducibility に対して、クラス C での最大元をC 完全問題と呼び ます。CNP はNP 完全問題 と言います。
次回は NP 完全問題についてお話します。