第 3 回計算量理論(2)

本日の内容

3-1. 前回の復習
3-2. 計算量理論(2)

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

3-1. 前回の復習

ポイント

問題の難しさをプログラムの使用する資源量により比較するのが計算量理論です。比較の仕方として、少なくとも必要な資源量を求める Lower bound と、具体的なプログラムを与えて十分な資源量を求める Upper bound と、多項式時間関数を使った reducibility を使って比較する方法があります。

プログラムの使用する資源量を求めるのに、実際のプログラムを特定状況下で実行させて実時間を計るのは無意味です。意味のある計り方は、入力の長さをパラメータ n とし、任意の長さに対して動作するプログラムの実行時間をパラメータ n のオーダ表示をする必要があります。

reducibility が閉じている問題のクラスは資源の使用量の関数が合成により閉じている必要があります。この条件を満たす問題のクラスには次のものがあります。

多項式時間 P
多項式領域 PSPACE
指数時間 EXPTIME

P は実用的な時間で解ける問題のクラス、EXPTIME は解くのに非現実的な時間のかかるクラスです。これは階層定理により異なることが示されています。 PSPACE には重要な問題が多く含まれていますが、 P とは異なると考えられています。

例3-1

次のプログラムの計算量を求めてみましょう。

バブルソート
```
#include <stdio.h>
void disparray(int *p){
  while(*p!=-1){
    printf("%d ",*p++);
  }
  printf("\n");
}
int main(void){
  int a[]={4,5,3,2,1,-1};
  int i,j,temp;
  disparray(a);
  for(i=0;a[i]!=-1;i++){
    for(j=1;a[j]!=-1;j++){
      if(a[j-1]>a[j]){
	temp=a[j-1];
	a[j-1]=a[j];
	a[j]=temp;
      }
    }
  }
  disparray(a);
  return 0;
}
```
ここでは簡単のために各 a[i] に入る数の大きさを考えず、a[i] に対する処理は全て 1 step であると仮定します。配列変数 a に入っている実データの個数を n と置く(一個一個のデータの長さも本当は議論しなければならないが、ここでは省略する)。 disparray は n 個のデータを順に出力するだけなので O(n)。 for(i...) も for(j...) も共に n 回、 n-1 回の繰り返し。 for の内部の処理はデータの個数に依らず一定時間でできる。従って、この for の二重ループは O(n²) 時間。再び disparray は O(n) 時間。従って、全体では O(n²) 時間。
エラトステネスのふるい
```
#include <stdio.h>
#define N 100
int main(void){
  int flag[N]={0};
  int i,j;
  for(i=2;i*i<N;i++){
    if(!flag[i]){
      for(j=2;i*j<N;j++){
	flag[i*j]=1;
      }
    }
  }
  for(i=2;i<N;i++){
    if(!flag[i]){
      printf("%d, ",i);
    }
  }
  printf("\n");
  return 0;
}
```
ここではデータそのものの長さも考えます。まず、桁数 n の足し算 (x+y) の計算量は筆算を各桁ごとに足すことを考えると、数の長さに比例した時間かかります。従って、 O(n) となります。

次に、桁数 n のかけ算 (x*y) の計算量も同様に筆算を考えます。二進数の筆算を考えると、x を y の桁数分だけ一桁ずつずらし、それらを全て足すのが手順です。かけ算の答えの長さは x の長さと y の長さを足した分だけになるので (log xy = log x + log y)、一方一回の足し算のコストはO(log x + log y)=O(n) です。また、足し算の回数は y の桁数なので、 log y = n。従って、かけ算にかかる時間計算量は O(n²) となります。

さて、プログラムの計算量を求めます。 N の長さは log N なので、これを n と置きます。まず、最初の部分で配列の宣言時に配列を初期化しています。この配列には 0 か 1 しか入らないので、領域は O(N) です。次に、for の実行回数は i*i が N になるまでなので、 $\sqrt{N}$ 回となります。また、このとき、毎回 i*i を計算しますが、この計算量は O(n²) です。さて、flag[i] が 0 の時、内部の for 文が実行されます。 flag[i] は i が素数のときに 0 になるので、実行回数は N 以下の数の中で素数の数になります。これは素数定理よりほぼ N/log N 個です。このとき、内部の for 文の繰り返し回数は O(N) 回です。従って、求める時間計算量は次の通りです。

$O (N) + O (\sqrt{N} n^{2} \frac{N}{log N} N)$
$= O (n 2^{\frac{5}{2} n}) = 2^{O (n)}$

NP という問題のクラスは P と PSPACE の間にあります。このクラスに属する問題には多くの最適化問題が含まれているため、実用上重要な問題のクラスです。 NP は後で述べますが、現実の計算機モデルにより定義されているわけではありません。 NP に含まれる問題がが現実の計算機モデルにおいてどのような計算量で計算できるかはまだ未解決です。これが数学の７大問題の一つ「P=NP?」問題です。つまり NP に含まれる問題全ては現実のコンピュータで多項式時間で解けるか解けないかという問題が、何十年にも渡り議論されています。この問題に対して、クレイ数学研究所から100万ドルの賞金がかけられています。今のところ P≠NP ということが広く信じられています。つまり NP の中でも難しい問題は、現実のコンピュータでは多項式時間で解けないだろうと言う認識です。しかしまだ決定的なことはよくわかっていません。

NP に含まれる問題とは次のようなものです。 NP の問題とは基本的に「決定問題」と言われるもので、例題(instance)が「yes」か「no」かを判定するものです。問題 A に対して、多項式時間計算可能な二変数関数 f(x,y) と、多項式 p(n) が対応し、例題 x が yes か no かを次のように判定します。

x が yes ( $x \in A$ ): 長さが p(|x|) 以下のある y が存在し、 f(x,y) が p(|x|) 時間以内で 1 を出力する。
x が no ( $x \notin A$ ): 長さ p(|x|) 以下で f(x,y) が p(|x|) 時間以内で 1 を出力するような y は存在しない。

ここで、NP に含まれ(Pに含まれないと思われている)いくつかの問題を紹介します。

ナップザック問題

インスタンス

荷物のサイズの集合 $X = \{x_{1} x_{2} ... x_{n}\}$
ナップザックのサイズ S

質問

$S = \sum_{x \in Y} x$ を満たす $Y \subseteq X$ が存在するか？

f(x,y) の構成

y として Y そのものを与え、

Y \subseteq X

と

S = \sum_{x \in Y} x

が成立したら 1 を出力、そうでなければ 0 を出力する。

巡回セールスマン問題

インスタンス

都市の集合 $X = \{お茶の水, 新宿, 池袋\}$
交通費リスト $t (お茶の水, 新宿) = 230$
予算 B

質問

予算以内に全都市を回ることができるか？

f(x,y) の構成

y として巡回リスト

L = (x_{1} x_{2} ... x_{n})

を与える。これに対して、 L が X の順列の一つであることと、

\sum_{i = 1}^{n - 1} t (x_{i}, x_{i + 1}) \leq B

が成立すれば 1 を出力し、成立しなければ 0 を出力する。

三色問題

インスタンス: 地図
質問: 地図を3色で塗り分けることができるか？
f(x,y) の構成: x として国のリストと、国境のリスト $((国_{1}, 国_{2}) ...)$ を与える。 y として、国の色リスト $((国_{1}, 色_{1}) ...)$ を仮定する。そして、色が三色しか使われてないことを確認し、全ての国境が異なる色になっているのであれば 1 を出力し、そうでなければ 0 を出力する。

補足

平面上の地図は 4 色で、ドーナツ上(地図の北と南、西と東がくっついている)では 7 色で必ず塗り分けられることは証明されています。

これらの問題の特徴は、ナップザックに入れる荷物のリスト、都市を回る順番、具体的な塗り分け方などがわかると多項式時間で yes であることが検証できることです。これが NP に属する問題の特徴です。一方、 PSPACE に属する(NPに含まれないと思われている)ゲームの必勝手順のように、たとえ必勝手順がわかっていても、それが「必勝」かどうかを検証することが難しい問題は NP 問題ではないと思われています（NP=PSPACE? も未解決問題なので、必勝手順は NP に含まれない可能性も含まれる可能性もあります)。

NP の計算

NP を二変数関数で存在条件で定義するのも正式な定義です。しかし、他の定義方法もあります。ここでは、別の定義を示します。

Turing 機械

.*aab

まずオートマトンについて復習します。オートマトンは状態遷移図のようなものです。オートマトンに与えられる文字に対して、次の状態が唯一決定するものを決定性オートマトンと言いました。一方、次の状態が複数ある時非決定性オートマトンと言いました。非決定性オートマトンでは、次の状態が複数ある時、全てを考慮し、入力文字を読み終えたときに一通りでも受理状態に遷移する状態があれば入力を受理しました。

非決定性オートマトンにおいて、次に遷移する状態を選択する代わりに、遷移可能な状態の集合を考えることにより、決定性オートマトンに変換することができました。したがって、受理する能力に関しては、非決定性オートマトンは決定性オートマトンと同等でした。

Turing 機械はオートマトンに片無限(左側は有限、右側は無限)のテープが付いたものです。 Turing 機械において、状態遷移図は次のように使われます。

テープの内容により状態を変化させます。
テープに文字を書きます。
テープのヘッドを左、または右に移動させます。

これは正式な記述では次のようになります。現在の状態が q、テープで読み込んだ文字を a とした時、上記の状態遷移により、状態を q' とし、テープに b を書き、テープヘッドを右に移す時、この遷移を表す記述を δ(q,a)=(q',b,右) と書きます。

全ての状態において、テープの文字に対してこのような状態が唯一決定するような Turing 機械を決定性 Turing 機械と言います。一方、一つのテープの文字に対して複数の状態遷移がある Turing 機械を非決定性 Turing 機械と言います。非決定性 Turing 機械では複数の計算が考えられますが、入力を受理する(つまり入力を yes と判定する)とは受理状態になる計算が一つ以上存在することを言います。

非決定性 Turing 機械の動作はオートマトンとテープの内容により決定されるので、決定性 Turing 機械へオートマトンと同様には変換できません。但し、一定時間内の非決定性 Turing 機械の動作は時間をかければ全て計算できるので、計算可能性理論的には差異はありません。従って、この非決定性は計算量理論特有の話題です。

このように非決定性 Turing 機械を定義すると、 NP の定義は次のようになります。問題 A が NP に属するとは次の条件が成り立つような非決定性 Turing 機械 M と多項式 p(n) が存在することです。

例題(インスタンス)x が A に含まれる時、 p(|x|) 時間以内に M(x) が受理状態になる計算が存在する。
例題(インスタンス)x が A に含まれない時、 p(|x|) 時間以内に M(x) が受理状態になる計算が無い。

つまり、 NP は Nondeterministic Polynomial Time のことです。

手続き型言語

アルゴリズム理論ではアルゴリズムを記述するのにしばしば ALGOL という C 言語や Pascal, Delfhiの祖先の言語を使用することがあります。但し、 ALGOL 特有の機能は使わず、ブロックを begin, end、制御を if や for であらわすだけです。アルゴリズム理論で非決定性のアルゴリズムを記述するのに、上で説明した、二変数関数や非決定性 Turing 機械を使うより、 ALGOL 言語に非決定性の命令を追加して記述するのが普通です。これは以下の命令です。

accept: 受理状態になり停止します。
reject: 拒否状態になり停止します。
guess: なるべく accept になるような都合の良い値を生成します。

例3-2

一般に最適化問題は次のように解きます。入力 x が評価値 c 以下の最適化が可能かどうかを調べるとします。

x を入力する
最適解 y を guess する
x が y の最適解かどうかチェックする
y による最適解が c 以下なら accept する
そうでなければ reject する

NP完全

NP の中で最も難しい問題を考えるため、 polynomial time many-one reducibility により、完全問題を考えます。

A が NP 完全問題

\Leftrightarrow (\forall B \in NP) [B \leq_{m}^{p} A]

つまり、 x が B に含まれるかどうかを調べるのに、 x を変形すると A に含まれるかどうかに帰着できます。

自明な NP 完全問題

次の定義により自明な NP 完全問題 L を示します。

$⟨i, x, j⟩ \in L$: i を非決定性 Turing 機械を記述する Gödel 数と解釈する。この非決定性 Turing 機械を M_i とする。これに x を入力した時、 |x|^j+j 時間内に受理状態になる計算が存在する。
$⟨i, x, j⟩ \notin L$: 上記の条件を満たさない時

この L に、任意の NP 問題 B が polynomial time many-one reducible であることを示します。 B が NP 問題であるとは、ある非決定性 Turing 機械 M と多項式 p(n) が存在し、 B に含まれる x に対しては M(x) が p(|x|) 時間以内に受理する計算が存在することをいいます。この時、M の Gödel 数を i、p(n)=O(n^j) とした時、 x が B に含まれるか否かは $⟨i, x, j⟩$ が L に含まれるかどうかを調べればわかります。 B が決まれば、i,j は x に依らず決まった値になりますので、この i,x,j の組を求めるのは多項式時間でできます。したがって、 $B \leq_{m}^{p} L$ が示せたことになります。

Cook の定理(1960)

論理式の充足可能性問題は NP 完全である。

論理式の充足可能性問題とは

論理式の各変数に True または False を割り当てた時、論理式が True になる割当が存在する時 yes, そうでなければ no を答える問題。これを SAT(Satisfiablity) と呼びます。

$(x_{1}⋁ x_{2}) ⋀ (\overline{x_{1}}⋁ \overline{x_{2}})$ に対して、 x₁=True, x₂=False とすると、この論理式は True になるので、充足可能です。

証明のアイディア

$L \leq_{m}^{p} SAT$ を示します。

非決定性 Turing 機械は入力 x に対して、 |x|^j+j 時間以内には、高々 |x|^j+j 個のテープしか使わない。
従って、|x|^j+j 時間以内の非決定性 Turing 機械の状況(状態+テープの内容 configuration)は、あらかじめ決められた数の状態と、 |x|^j+j マスのテープの内容により決定する。
非決定性の Turing 機械の状況が高々 O(|x|^j+j) bit で記述できるので、各桁を論理変数に割り当てる。
この論理変数の列を |x|^j+j 時間分用意する。
$(初期状態と最初のテープの状況) ⋀ \underset{t}{⋀} \underset{k}{⋀} (時刻 t の状況の k 桁目の満たす条件) ⋀ (受理状態に入る)$
この条件を満たすような論理変数への値割当が存在する時、実際に多項式時間で受理する計算が存在することになるので、 x∈L が成り立つ。

その他の NP に関する話題

良い近似が存在しないかも(Arora 1992)

NP 完全問題を良い近似で解くアルゴリズムが存在すれば P=NP

素数判定(2002)

素数判定は決定性多項式時間で解ける

但し、素因数分解はまだ決定性の多項式時間のアルゴリズムは見つかってない。非決定的に素因数を guess して割り切れるか確かめればできるので、非決定的には多項式時間でできる。

離散対数問題

入力: x,y, 素数 p
出力: x^z-y が p で割り切れるような z
$x^{z} \equiv y (mod p)$

グラフ同型問題

二つのグラフ G₁=(V₁,E₁), G₂=(V₂,E₂) に対して、頂点同士の一対一写像を与えた時、同一のグラフになる時、二つのグラフは同型と言います。これは非決定的に一対一写像を guess して、グラフの構造を調べればいいので、非決定的には多項式時間でできます。しかし、この問題に関しては NP 完全ではないと思われるさまざまな状況証拠が見つかっています。

坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科

第 3 回 計算量理論(2)