第 9 回 非決定性(2)、完全問題

本日の内容

• 9-1. 非決定性の計算のクラスの関係
• 9-2. P, NP
• 9-3. 完全問題
• 9-4. 宿題
• 9-5. 次週の予告
• 9-6. 付録

9-1. 非決定性の計算のクラスの関係

始めに時間限定、領域限定の言語のクラスを定義します。

1. Dtime(p(n))を入力の長さ n に対して決定性で p(n) 時間で 受理できる言語のクラス
2. Ntime(p(n))は入力の長さ n に対して非決定性 p(n) 時間で受理できる言語のクラス
3. Dspace(p(n))は入力の長さ n に対して決定性 p(n) 領域で受理できる言語のクラス
4. Nspace(p(n))は入力の長さ n に対して非決定性 p(n) 領域で受理できる言語のクラス

なお、線形加速定理により、 Dtime(p(N))=Dtime(O(p(N))。

各クラス 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 を入れ換えた時、次のようになってしまいます。

x が L に含まれる時

x を reject する計算が存在する。しかし accept する計算が存在しても構わない。

x が L に含まれない時

全ての計算で x を accept する。

この場合、あらゆる入力に対して accept してしまうかも知れません。 前に示した、合成数判定問題で accept と reject を交換しても素数判定がで きないことを示します。合成数判定問題を解く非決定性のプログラムに対して、 機械的に accept と reject を交換したものを考えます。

1. guess x(2≦x≦√nの切り上げ);
2. if( n が x で割り切れる) { reject; } else{ accept; }

これが、29以上の nで accept することを示しま す。

定理

29 以上のすべての nは 2から√nの切り上げまでの間で少なくとも一つ以上の nを割り切らない数が存在する。

証明（電気電子専攻 柴田透君による）

補題

m≧5 なら、 $\mathrm{lcd}(m,m-2)=m\left(m-2\right)\text{or}\frac{m\left(m-2\right)}{2}$

補題の証明

mが奇数の時、 $\mathrm{lcd}(m,m-2)=m\left(m-2\right)$ を示す。

もし、そうでないとすると、 $\gcd (m,m-2)=g$ (g≧3) なる g が存在する。

そこで、mをgで割った商をdとすると、 m=gdより、 $\left(m-2\right)=gd-2=g\left(d-\frac{2}{g}\right)$ 。 ところが、dは整数なので、gは 2を割り切らなけれ ばいけない。これは、g≧3に反するので矛盾。

偶数の場合も同様■

補題

m≧5 なら、 $\mathrm{lcd}(m,m-1,m-2)=m\left(m-1\right)\left(m-2\right)\text{or}\frac{m\left(m-1\right)\left(m-2\right)}{2}$

補題の証明

前の補題と同様に m, m-1, m-2 のどの二つの組み合わせの gcd も 3より大きくならないこ とと、偶奇を考慮すれば良い■

補題

$m>\frac{5+\sqrt{33}}{2}$ なら、 $m^2<\frac{m\left(m-1\right)\left(m-2\right)}{2}$

補題の証明

式を変形すると次を得る。

したがって、 $m>\frac{5+\sqrt{33}}{2}$ ならば、与式は満たされる。■

定理の証明

nに対して、√nの切り上げをmとする。 すると、 $m^2\ge n>{\left(\frac{5+\sqrt{33}}{2}\right)}^2\sim 28.86$ の時、 $n\le m^2<\mathrm{lcd}(m,m-1,m-2)$ が成り立つ。 n は m, m-1, m-2 の lcd より真に小さいので、この3つの数の少なくとも一 つは約数に持たない。 したがって、m以下で nを割り切らない数が存在す る■

なお、29未満の数に関して、具体的に調べると、reject するのは 2, 3, 4, 6, 12 のみです。したがって、このプログラムでは、素数を判定 することはできません。

このように、非決定性の計算では、クラス C とクラス co-C が等しいかどう かは自明ではありません。 ここでは、ここに示したクラスの関係を調べます。

非決定性では、入力が一つ決まっていても、次の状態が複数あります。 非決定性の Turing 機械に対して、様相を考えると、次の瞬間の様相が複数個 存在します。 但し、 状態やテープに書き込める文 字やテープヘッドの移動がそれぞれ有限の場合しかないので、 1 Step に移ることが可能な様相の数は高々定数個です。 これは一般性を失わず 2 個に制限することができます。 様相を考えると、非決定性の計算は初期状態を根とした木になります (但し、別々の計算から同じ様相に合流することは無視しています)。 これを計算木と言います。 計算木の考え方を使うと、次のことを示すことができます。

1. Ntime(p(N))⊆Nspace(p(N))
2. Ntime(p(N))⊆Dtime(2^p(N))
3. Nspace(p(N))⊆Dspace(p(N)²)(Savichの定理)
4. Nspace(p(N)) = co-Nspace(p(N))(Immerman–Szelepcsényi)

Ntime(p(N))⊆Nspace(p(N))

p(N) 時間には高々 p(N) 領域しか使えないので明らか

Ntime(p(N))⊆Dtime(2^p(N))

非決定性の Turing 機械が p(N) 時間限定である時、計算木の深さは p(N) に なります。 非決定性に次の状態へ移ることが可能な状態が高々 2 個とすると、木の葉の 数は高々 2^p(N) になります。入力が一つ決まれば決定性の計算 で計算木は一つに決定されます。そこで、決定性の計算で初期様相から木の葉を depth-first-search して、全ての木の葉をチェックすることができます。 この時、depth-first-search にかかる時間は木を構成する辺の数の高々定数 倍になります。 従って、 辺の数が 2+4+...+2^p(n) = O(2^p(N)) になるので、 全ての木の葉を調べ、一つでも accept する計算が存在するかどうかを計算し て yes か no を出力する計算が計算する言語は Dtime(2^p(N)) に 含まれます。

演習9-1

Savich の定理 Nspace(p(N))⊆Dspace(p(N)²) を証明しなさい。

ヒント

accept する様相をバックトラックを使って検索します。

p(N)≥log N ならば Nspace(p(N))= co-Nspace(p(N))(Immerman–Szelepcsényi)

始めに、Nspace(p(N))の言語を L とし、それを p(N) 領域で受理する Turing 機械を M とします。 また、長さ n の入力 x を M に与えたときの様相の数が d^p(n) で抑えられるとします。 つまり x∈L であれば、 M(x) は d^p(n)=D 時間以内に accept します。

補題:

NSpace(p(N))計算の Turing 機械に対して、入力 x を与えたとき、 t 時間以内に到達できる様相の数は非決定性 p(N) スペースで計算できる。

証明

計算ステップに対して、帰納的に遷移可能な様相の数を 非決定性 p(N) スペースで計算できることを示します。 p(N) スペースの計算は高々 2^p(N)ステップ以内に終了するので、 これを示せば、 p(N) スペースで遷移可能な様相の数を出力できます。

まず1ステップ目は初期様相は一つしかないので 1 を出力すればよく、これ は p(N)スペースで計算できます。

次に、 t ステップ以内では遷移可能な様相が m 個だと分かっていたとき、 t+1 ステップでの遷移可能な様相の数が出力できることを示します。 基本的なアイディアは、 p(N) スペースの非決定性の様相をシミュレートす るのに、計算を順に行うのではなく、数が分かっている限り、その数の様相 を非決定的に選べるということです。

1. t ステップ以内で遷移可能な m 個の様相全てを捉えるには、次のように行 います。

   アルゴリズム1

   1. 選ぶ様相を数えるためのカウンターを 0 とします。
   2. すべての様相 i に対して次を行います
      1. 非決定的に採用するかしないかを選びます
      2. 採用しなければ次のステップに進みます
      3. 採用するなら、カウンターを1増やし、 様相 i が初期様相から t ステップ以内に非決定的に到達可能かを非決定的な計算で確認しま す
   3. すべての様相について調べた後、カウンターが m と等しければ accept します

   到達可能な様相が m であるのであれば、そのすべての様相だけを採用した ときだけ accept にたどり着けます。

2. 次にこれを利用してt+1ステップで到達できる様相を数え上げる。 これには、すべての様相 j に対して、 t ステップで遷移可能なm 個の様相 i のどれかから 1 ステップで遷移可能かどうかをチェックすれば良い。 これをアルゴリズムで記述すると次のようになる

   アルゴリズム2

   1. t+1ステップで到達できる様相を数えるカウンターを0とする
   2. すべての p(N)スペースの様相 j について、以下を行う
      1. 遷移可能であるという論理変数を偽にします
      2. すべてのp(N)スペースの様相 i について以下を行う
         1. 初期様相から i までt ステップ以内で遷移可能 であることをアルゴリズム1により確認します
         2. i から j までに1step で遷移可能かを決定的に確認し、遷移 可能ならその論理変数を真にします
      3. 遷移可能を示す論理変数が真なら、様相を数えるカウンターを1増やしま す。
   3. 様相を数えるカウンターを出力し、accept します

   各 j に対して、 t ステップ以内で遷移可能な様相 i は全て正しく選ばれ るので、t+1 ステップで遷移可能な j は全て正しく数え上げられます。

以上により、 1 からスタートして、 D まで順にアルゴリズム2を実行する と、2^p(n)ステップまでに遷移可能な様相を全て数え上げられま す。これは p(n) スペースで遷移可能な様相を全て数え上げたことになりま す。

補題:

NSpace(p(N))計算の Turing 機械に対して、入力 x と制限時間 t と到達 可能な様相数 m を与え たとき、 t 時間以内に到達できるすべての様相が m 個であれば、受理様相が無いこと を非決定性 NSpace(p(N))で 検出できる

証明

基本的には前補題と同様です。 m が分かっていれば t ステップ以内に遷移可能な様相は全てもれなく選べる ので、すべての遷移可能な様相を調べて受理様相の数を数えることができる。

定理の証明

1. D 時間以内に到達可能な様相の数を非決定的に求め m とする。
2. D 時間以内に到達する m 個の様相全てについて受理様相の数を数える
3. 受理様相が一個もなかったら accept する

上記が正確に数を数えられ、しかも、 x が L に含まれていないときだけ accept し、すべての計算が O(p(N)) space の Turing 機械が実効で切るこ とが分かる。

9-2. P, NP

多項式時間

問題の難しさを大雑把に評価することを考えます。 具体的には「実用的な時間で求められる」「実用的な時間では求められない」 など「解ける」「解けない」に直観的に近い感覚を考えます。 そのためにはどんな考え方を導入すればいいでしょうか?

コンピュータプログラムで作成した関数を複数回利用することを考えます。 作成した関数を c(x)、c(x) を計算する時間を t(|x|)、c(x) を計算するのに 必要な領域を s(|x|) とします。 また、別の関数を f(n) とします。

複数回単純に呼び出す

c(x₁), c(x₂)...

for文で f(|x|) 回呼び出す

for(i=0;i<f(|x|);i++)c(x_i)

c(x) とは別の関数 c' の出力 c'(x) に対して c を求める。

c(c'(x))

このようにすると、それぞれの計算時間は t(|x|)の定数倍、f(|x|)t(|x|)、t'(|x|)+t(|c'(x)|) となります。 一方、領域の使用量は s(|x|) の定数倍、 max{s(|x_i|)}、 max{s'(|x|),s(|c'(x)|)} になります。

t(n),t'(n),f(n) が多項式であるなら、このような定数倍、和、積、合成に閉じて ますので、結果も多項式になります。 また、指数関数は定数倍、積に対して閉じてます。 一方、単なる c n も定数倍、合成について閉じています。 複数の問題をプログラムで比較するのに、このような関数の性質が あると便利です。 そこで、大雑把な問題の複雑さのクラスとして、直観的な意味を含め次の概念 を導入します。

リニアタイム(線形時間)

入力の長さの定数倍の時間で解ける問題のクラス。入力を読む手間程度で 解けるので簡単な問題

多項式時間

入力の長さに対してある多項式で抑えられるような計算時間で計算できる 問題のクラス。実用的な時間で解ける問題のクラス

指数時間

入力の長さに対してある指数関数で抑えられるような計算時間で計算でき る問題のクラス。実用的には手に負えない問題。

同様にして線形領域、多項式領域なども定義できる。

P,NP

今までの Turing 機械で定義した問題のクラスと、前節で議論した多項式時間 などの概念を元に、厳密な(かつ大雑把な)問題のクラスを定義します。

• P= ∪ Dtime(n^c)
• NP= ∪ Ntime(n^c), co-NP={ L | Σ^* - L ∈ NP }
• PSPACE=NPSPACE= ∪ Dspace(n^c)
• EXPTIME = ∪ Dtime(2^nc )

これらの関係でわかっているのは次の通りです。

• P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
• P ≠ EXPTIME

特に、 P が NP と等しいのか異なるのかは計算量理論の中で最大の未解決問 題です。

演習9-2

P≠EXPTIME を階層定理を用いて示しなさい。

9-3. 完全問題

Reducibility

問題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 は通常≦_m^p と書きます。但し、誤解を招かない限り≦のみを使うことがあります。

素朴な完全問題

半順序では、任意の二つの要素が比較可能かどうかはわかりません。 そこで、どんな要素に対しても小さい要素(最小元)やどんな要素よりも大きい 要素(最大元)が存在するかを調べます。

まず、最小元ですが、問題 A: 「入力が 0 なら no。それ以外は yes」のよう な yes, no のどちらかが有限集合になっているものが考えられます。 その理由は、どんな言語 B を持ってきても、A ≦_m^p B が成り立つからです。 任意の問題(言語) B を考え、x₀ が B に含まれず、 x₁ が B に含まれるとします。 すると、「入力が 0 なら x₀、 それ以外なら x₀」と いう reduction を考えると many-one reducibility になります。

一方、最大元は次のようにすれば各計算のクラスで存在することが分かります。 但し、ここには示しませんでしたが、完全問題が存在しなさそうなクラスもあ ります。

1. C_P={ (i,x,c) | コードが i の決定性 Turing 機械に入力 x を与え、高々 |x|^c+c ステップ実行した時 1 を出力する }
2. C_NP={ (i,x,c) | コードが i の非決定性 Turing 機械に入力 x を与え、高々 |x|^c+c ステップ実行した時 accept する計算が存 在する }
3. C_EXPTIME={ (i,x,c) | コードが i の決定性 Turing 機械に入力 x を与え、高々 2^|x|c+c ステップ実行した時 1 を出力する }

例えばある問題(言語) L が NP に含まれるとします。 すると、定義より L を計算する非決定性の Turing 機械が存在し、入力 x の長さ に対して、その計算時間を制限する多項式 p(|x|) が存在します。 これは、問題を一つ決めると Turing 機械も多項式も一つ決まります。 すると、その Turing 機械のコードを i, p(n)≦ n^c+c が常に成り立つよ うな定数を c が得られます。 これにより、任意の入力 x に対して、 (i,x,c) を考えると、C_NP を利用して L を解くことができます。 従って、 L ≦ C_NP が言えます。

reducibility に対して、クラス C での最大元をC 完全問題と呼び ます。 例えば、「C_NP はNP 完全問題 である」などとと言い ます。

9-4. 宿題

NP 完全問題の一つが決定性多項式時間で解けたら、P=NP であることを示しな さい。

9-5. 次週の予告

次回は NP 完全問題についてお話します。

9-6. 付録

Savich の定理

領域に関する階層定理と同様に、p(N)領域限定の非決定性の機械の可能な様相 の数も高々 2^p(N) になります。 また、使う計算時間も高々 2^p(N) になります。 ここで、問題は初期様相から受理様相まで長さ 2^p(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 個の頂点情報が記憶できる時、距離 2^k まで調べること ができます。 最長の計算時間が 2^p(N) なら、記憶する頂点情報は高々 p(N) 個 あれば十分なので、様相の長さと必要な個数の積が求める記憶容量になります。 従って、p(N)² 領域あれば、受理様相への計算が存在するかを計 算することができます。