計算量理論のバックアップ(No.6)

講義日程-2007年度冬学期

計算量理論(Computational Complexity) †

担当：今井浩教授
1.5単位
- 数理：限定選択B
10:15～11:45 理学部７号館(化学教育東館)236号室
参考書
- Michael R. Garey and David S. Johnson
  Computers and Intractability
  A Guide to the Theory of NP-Completeness
  W.H.Freeman and Co. NY. 1979

↑

内容 †

計算量理論とは、計算の難しさの学問。
- 例）n都市TSP
  n頂点の重み付き単純グラフ上の閉路で、各頂点をちょうど一度ずつ訪れる。
  辺の重みの和を最小にする閉路を求める問題。
  有限・離散なので解は有限時間内に計算可能。
  しかしそのために必要な計算量は指数オーダー。
  nが大きくなると実用時間内では実行不可能。
  - 素朴な解法
    (n-1)!通りの巡り方での距離を全て計算・比較。
    路一つあたりの計算量が10^(-6)sでも、n=50くらいで計算量は10^50年。
  - cf)ある頂点から他の全ての頂点への最短路を求める問題はO(|V|^2+|E|) Dijkstra's Algorithm
  - TSPはどんなアルゴリズムでも、(最悪の場合)O(n^c)で解くことはできなさそう。NP問題
     ミレニアム懸賞問題,P≠NP問題

NP完全性の理論
- NP:Nondeterministic Polynomial,非決定性多項式時間

n要素全順序集合のソーティング
- Insert Sort O(n^2)
  - n個の整列されたリストにn+1個目の要素を適切な場所に挿入する。
- Bubble Sort O(n^2)
  - リストから順序関係が壊れている部分を探し、正す。
- Heap Sort O(n log n)
  - 要素からヒープツリーを作って、取り出す。
- Quick Sort 平均的にはO(n log n)、最悪ではO(n^2)
  - 中間要素を選び、それより大きい部分リストと小さい部分リストを選び出し、連結する。
- Merge Sort O(n log n)
  - 分割統治。リストを二つに分け、それぞれをソートし、順序の整合が取れるようにマージ。
- どんなアルゴリズムでもΩ(n log n)の時間がかかる。
  (memo:データに制約をつければO(n)にもなりうる。Radix Sort)

Linear Decision Tree
- プログラムの実行パスをツリーの形で全て書き表したもの。
  葉の部分に実行結果が現れる。
  Insent SortのLinear Decision Treeの高さは有限。
  各比較について分岐が一つできる。
  最も木の高さが高くなる最悪のパスでは、O(n^2)になる。
- 正しいソーティングアルゴリズムでは、出力になり得る組み合わせはn!通り。
  木の高さをできるだけ低くして葉の数を増やすことを考えると、
  (深さ)≧ceil(log[2](n!))=O(n log n)
  二要素の比較だけを使ってソートするときの計算量の下限はO(n log s)
  Linear Decision Treeで表したときにバランスの取れた二分木になるようなアルゴリズムが最良のソーティングアルゴリズム。

行列積
- A,B ∈ R^(n×n)
  C = AB
  c[i][j] = Σ[k=1,n]a[i][k]b[k][j]
  式をそのまま計算すると、O(n^3)
  これより計算量の少ない計算方法は存在するだろうか？
- 行列をうまく分割して計算するとO(n^log[2]7)≒O(n^2.807)で計算できる。Strassenのアルゴリズム
- 現在ではO(n^2.386)まで下げられている。下限はΩ(n^2)以上だとしかわかっていない。

漸近的性質
関数f,g:N⇒Nについて
- O
  f(n) = O(g(n))⇔∃n,∃c,∀m≧n. f(m)≦c*g(m)
- Ω
  f(n) = Ω(g(n))⇔∃n,∃c,∀m≧n. f(m)≧c*g(m)
- Θ
  f(n) = Θ(g(n))⇔f(n)=O(g(n))∧f(n)=Ω(g(n))
- o
  f(n)=o(g(n))⇔lim[n→∞]f(n)/g(n)=0

入力サイズnについて、アルゴリズムAの計算時間t(n)がどう増えてゆくか。
- P: t(n)がnの多項式のオーダーとなるアルゴリズムが存在する問題族
  多項式オーダー：O(n^c),
  n,n log(n),n^2,√n,…
- EXP:t(n)がnの指数関数のオーダーとなるアルゴリズムが存在する問題族
  指数関数オーダー(singly exponential):O(2^p(n)),p(n)=O(n^c)
  2^n,n!,n^n=2^(n log(n)),3^(n^2)
- P⊂EXP, nを十分に大きくすると常にEXPの問題の方が大きくなる。
  EXPに属する問題は手におえないくらい計算時間が長くなる。
  P:tractable 手に終える
  Pより上:intractable 手に負えない
  ではEXPとPの境界はどこにあるか。
  それより難しい問題はどう解くか。

計算の難しさ。（上に行くほど難しい。）
- undecidable:計算不能、アルゴリズムが存在しない。
  Turing Machineの停止問題
- decidable:計算可能、アルゴリズムが存在する。
  - 多重指数オーダーで解ける。 Presburger Arithmetic
- intractable:実行不可能、多項式オーダーでは解けない。
  - NP完全問題。非決定性チューリングマシンで多項式オーダーで計算できる。
    境界はまだ曖昧。
    TSP,SAT,coloring
- tractable:実行可能、多項式オーダーで解ける。

アルゴリズムとは何か
- 計算とは、状態遷移だ。
  - Turing Machine
    有限長のプログラム(内部状態)と無限の長さの一次元記憶媒体(テープ)を持った仮想的な機械。
  - TM=(Γ,Σ,Q,δ)
    Γ=Σ∪{b} テープのセルに書く記号の集合。
  - Σ 問題を記述する記号の集合。alphabet
  - Q 機械の内部状態の集合。有限。
    q[0]：初期状態
    q[y]：停止状態、受理
    q[n]：停止状態、非受理
  - δ:Q×Γ→Q×Γ×{+1,-1} 遷移関数。現在の状態と現在地のテープの記号から、
    次の時刻の状態とテープに上書きする値、テープ上の位置の変化を出す関数。
  - 初期状態から、遷移関数に従ってテープ上に記録されたデータを書き換えながら
    内部状態とテープ上の位置を変化させ、停止状態になるまで動き続ける。
    停止状態になったらyes,noのいずれかを返す。
    停止しないこともありうる。
    テープ上に入力を与え、出力としてyes,noを返す計算のモデル。
  - 現在のコンピュータで多項式時間で解ける問題はチューリングマシンでも多項式時間で解ける。逆も成立。
  - δが一価の関数→決定性チューリングマシン
    δが多価関数→非決定性チューリングマシン

決定性チューリングマシン(DTM,Deterministic Turing Machine)
- 通常のチューリングマシン。同じ入力に対して同じ出力を返す。遷移関数が一価関数。
- 計算資源、サイズnの入力に対して最悪の場合の量を指す。
  time complexity：遷移関数を適用する回数。
  space complexity：headが少なくとも一度見たセルの数。
- P：チューリングマシンでの時間計算量が、入力のサイズの多項式で押えられるアルゴリズムが存在する問題。
  PSpace：空間計算量が、入力のサイズの多項式で押えられるアルゴリズムが存在する問題。

PTime ⊂ PSpace ⊂ ExpTime
- 空間計算量がnの多項式で押えられる問題は、時間計算量はexp以下になる。
- 無限ループに陥らないアルゴリズムの実行中には、状態遷移の過程で、同じ状態になることはできない。
  空間計算量が多項式で押えられると、状態遷移で通過できる状態数は指数オーダーで押えられる。

非決定性チューリングマシン(NTM,Nondeterministic Turing Machine)
- 同時に複数の状態をとりうる、遷移関数が多価関数になりうる拡張されたチューリングマシン。並列計算のモデル化？
- 計算資源
  time complexity：NTMを次々に分岐させながらステップを進めて行き、最も早くyesを返して停止した分岐までのステップ数。
  space complexity：最も早くyesを返して停止した分岐での、少なくとも一度見たセルの数。
NP：非決定性チューリングマシンでの時間計算量が、入力サイズの多項式で押えられるアルゴリズムが存在する問題。

PTime ⊂ NP ⊂ PSpace
- NTMをDTMでシミュレート。各ステップを幅優先探索。
  バックトラックの状態復元に使うメモリは、深さが多項式オーダーなら、多項式オーダー。

並列計算をしたときや、計算機が速くなったときの、同一時間で解ける問題のサイズ。
- プロセッサ数がp倍になったときに、
  O(n) p倍
  O(n^2) √p倍
  O(2^n) log p倍。

多項式時間変換(Polynomial-time Reducibility)
- ハミルトン閉路(HC,Hamilton Circuit)問題
  入力:グラフ
  出力：入力グラフがHCを持つか否か。
- 巡回セールスマン問題の判定
  完全グラフ。距離関数。パラメタ一つ。
  総長がパラメタの値以下のHCが存在するかどうか。
- ある問題クラスΠの、任意のインスタンスが、別のあるクラスΠ'のインスタンスに多項式時間で帰着できるなら、
  ΠはΠ`に多項式時間変換可能だという。
  f:Π→Π'. π:yes⇔f(π):yes
- ハミルトン閉路問題は、多項式時間で巡回セールスマン問題に多項式時間で変換可能。
  完全グラフ化して、追加したグラフの重みを大きくしておく。

NTM(Oracle版)
- Guessing Module付きのDTM
- 入力xがセル1からセル|x|まで与えられている。
  「Advice」をGuessing Moduleがセル(-1)から左に書く。
  Guessing Moduleを停止してDTMとして起動。処理。停止。
- NTMでどの分岐をすべきかをあらかじめ外部から与えたもの。
- NTMを使うと多項式時間で解ける問題は、DTMで多項式時間で正解を検証できる問題。

命題論理の充足可能性判定問題(SAT,Satisfiability)
- 入力：CNF命題論理式(CNF,Conjunctive Normal Form,∧標準形)
- 出力：入力の論理式を満たす真偽値の組み合わせがあればTrue,なければFalse
- 入力は論理変数をn個持った論理式で、論理変数と￢と∨からなる節(Clause)を∧で連ねた形に標準化されたもの。
  うまく論理変数の値を選んだとき、論理式全体を真にできるとき、その論理式は充足可能。
  どの組み合わせを選んでも真にできないとき、恒偽、充足不可能と呼ぶ。
- この充足可能性問題は

ここLostかも。後で補完。

NPの中で多項式時間還元を考えることでNPを分類する。
多項式時間還元で擬順序を導き、擬順序から導かれる同値関係でNPを分割。
分割された塊の間には、多項式時間還元によって半順序が入っている。
この半順序には最小元と最大元が存在する。最小限はP、最大限はNP完全問題。
NP完全
NP問題クラス $\Pi$ のうちで、任意のNP問題クラス $\Pi'$ の問題を
多項式時間で $\Pi$ に帰着できるなら、
$\Pi$ はNP完全という。
NP完全な問題のどれか一つに多項式時間アルゴリズムが存在すれば、
任意のNP問題が多項式時間で解ける。 $P=NP$
NP完全な問題には多項式時間アルゴリズムは存在せず、
$P\neq NP$ だろうという考えが大勢になっている。
SAT,TSPなど、多くの問題がNP完全であることがわかっている。

Karpのreduction
- 問題クラス&mimetx(\Pi);がNP完全であることを示したいときには、
  $\Pi$ がNP問題であることと、適当なNP完全問題 $\Pi'$ を
  $\Pi$ に多項式時間還元ができることを示せばいい。
  ではどのNP完全問題に帰着できることを示すのがよいか。
- SATはNP完全。SATを他の問題に連鎖的に帰着させてNP完全性を示す。
  $\mathrm{SAT} \prec \mathrm{3SAT}$
  $\mathrm{3SAT} \prec \mathrm{3DM}$
  $\mathrm{3DM} \prec \mathrm{PARTITION}$
  $\mathrm{3SAT} \prec \mathrm{VC}$
  $\mathrm{VC} \prec \mathrm{HC}$
  $\mathrm{HC} \prec \mathrm{TSP}$
  $\mathrm{VC} \prec \mathrm{CLIQUE}$
- 3SAT
  入力：3-CNF論理式(各節が3つの命題からなる和積標準形の論理式)
  和積標準形論理式の節は、論理積で連なっている論理和からなる塊。
  出力：論理式を真にする命題の組み合わせが存在するか。
  - 3SATはNP問題。SATはNP問題。3SATはSANの部分クラス。
  - 任意のSATの問題を3SATに多項式時間還元できることを示せば、3SATがNP完全であることを証明できる。
    任意のSATの問題の各節について、
    節に含まれる論理変数の数が1,2,3のときには、新たに論理変数を追加して水増し。3変数にする。
    $x \equiv (x\vee y) \wedge (x \vee \bar{y})$
    論理変数の数が4以上。例えば5のときには、
    $a\vee b \vee c \vee d \vee e \equiv (a\vee b \vee x)\wedge(\bar{x}\vee c \vee y)\wedge(\bar{y}\vee d \vee e)$ と変形すれば3変数にできる。
    ゆえに任意のSATの問題は多項式時間で3SAT問題に帰着可能。
  - cf)2SAT
    入力を2-CNF論理式に限った2SATは $O(n)$ 、P問題。
- VC(Vertex Cover)。無向グラフの被覆問題。
  入力：無向グラフとパラメタK。
  出力：サイズK以下のVertex Coverが存在するか否か。
  - 3SAT問題をVCに帰着すれば、VCがNP完全であることを示せる。
    VCはNP問題。解が与えられればそれがサイズK以下の被覆になっていることは
    多項式時間で確かめられる。
    3SATの論理式をグラフに変換し、充足可能性とVCの存在が同値になるようにKを選ぶ。
    各論理変数とその否定を頂点とし、肯定形と否定形を頂点でつないで２点からなるグラフを作り、
    各節に対応して、その論理変数に応じた三角形のグラフを作り、
    節に対応するグラフの頂点と、それに対応する論理変数を繋ぐ。
    Kとして、(論理変数の数)+2*(節の数)をとってVC問題とすると、 3SATをVCに帰着できる。
  - Vertex Cover
    任意の辺の少なくとも一方が含まれるように、グラフの頂点からいくつかを選び出す。
  - cf)２部グラフについては、最小VC探索はP問題。最小VCは最大マッチングを与える。

先生会議中。代理の人が講義。
PSPACE = NPSPACE
- PSPACE
  決定性チューリングマシンで、入力サイズに対して領域計算量が多項式オーダーで計算可能。
- NPSPACE
  非決定性チューリングマシンで、入力サイズに対して領域計算量が多項式オーダーで計算可能。
- 有向グラフの連結性判定
  入力：有向グラフ。 $|V|=n$
  出力：頂点s,tを結ぶ長さが $2^k$ 以下の路があるか否か。
  - STCONのアルゴリズム
    長さが $2^k$ 以下の有向路があるか否かを返す関数reachを使って、
    $\mathrm{reach}(s,t,\log n)$ を実行すればよい。
    $\mathrm{reach}(v_1,v_2,k)\{$
    $\mathrm{if}(k=0)\{\mathrm{return}\ v_1 == v_2 \vee (v_1,v_2)\in E \}$
    $\mathrm{else} \{$
    $\mathrm{foreach}(v'\ \in V)\mathrm{return}\ \mathrm{reach}(v_1,v',k-1) \wedge \mathrm{reach}(v',v_2,k-1)$
    $\}$
  - 一回の再帰には $O(log n)$ の計算領域、再帰の深さは $O(log n)$ なので、
    計算領域は $O((log n)^2)$ だけ必要、PSPACE。
- PSPACE = NPSPACEの証明
  PSPACE $\subset$ NPSPACE は定義から自明。
  NPSPACE $\subset$ PSPACE を証明するために、
  チューリングマシンのスナップショットからなるグラフを考える、
  各スナップショットをノードにし、遷移規則から枝を定める。
  計算領域がNTMで $p(n)$ であるとすると、頂点数は、(状態数)*(使う領域幅)*(テープの内容)^(使う領域幅)で、 $O(e^{p(n)})$
  このグラフに対してTMでSTCONのアルゴリズムを走らせると、
  領域計算量は $O(p(n)^2)$ なので、TMで多項式空間計算量でシミュレート可能。
- STCONはNLOG完全。NTMでO(log(n))で計算可能。
- LOG $\subset$ NLOG $\subset$ (LOG)^2
- STCONが $\log n$ SPACEで計算可能かどうかは未解決。
- Randomized Algorithmなら $\log n$ SPACEで計算可能。
- 無向グラフなら $\log n$ SPACEで計算可能。

NP-Completeの意義
- P $\subset$ NP $\subset$ PSPACE=NPSPACE $\subset$ EXPTIME $\subset$ NEXPTIME
- NP完全問題が一つでもPであることがわかれば、P=NP。
  任意のNP問題がPであることがわかる。
- P問題はTractable、それ以外はIntractableだと考え。
  P=NPではないことを想定して、NP完全であることを示すことで、問題がIntractableであることを示す。
  NP完全であることを示すことがパラダイムになっている。

Ristriction
- NP完全な部分問題を含むNP問題は、NP完全問題。
  問題を限定した上でNP完全性を示し、全体の問題クラスもNP完全であることを得る。

部分グラフ同型判定問題
入力：無向グラフ２つ。 $G_1,G_2$
出力： $G_1$ が $G_2$ と同型な部分グラフを持つか否か。

CLIQUE
入力：無向グラフ。 $G$
出力： $G$ がサイズk以上の完全グラフを部分グラフを持つか。
- 同型になる部分グラフと同型写像が与えられれば、確かめることは多項式時間で可能。NP問題。
- CLIQUEは部分グラフ同型判定問題の部分問題。
  CLIQUEがNP完全ならば部分グラフ同型判定問題はNP完全。

Local Transformation
Component Design

NP完全性を示す事で、問題が難しいことを示す。
問題の簡単さを示すには、多項式時間で解けるアルゴリズムを見つければよい。
- SATはNP完全問題。
  3-SATもNP完全問題。
  2-SATはP問題で、O(n)で解ける。
  SATは節の中の論理変数の数で階層化できる。
  k-SATは、k=2ではP問題。k≧3ではNP完全問題。
  同様な階層化はk部グラフのマッチング問題でもできる。
  - HORN
    SATの部分問題。各節に正リテラルが高々１つ。P問題。O(n)で解ける。

難しさの異なる似た問題をNP完全か、Pかで類別する。
- 枝長非負なグラフの最短路問題はP問題。(Dijkstra法)
- 最長単純路問題はNP問題。
  単純路：同じ頂点を２度は通らない路。
  - 有向閉路のないグラフでの最長路問題はP問題。(DFS,topological sort)

グラフの最小点被覆
点による枝の被覆。NP完全問題。
グラフからいくつか点を選び出し、各枝について
その枝の端点のどちらかは選ばれるようにする。
選ばれる点数はできるだけ少なくする。
２部グラフの点被覆を求めるのはP問題。
- 最大マッチング・最小点被覆定理
グラフの最小枝被覆
枝による点の被覆。P問題。
グラフから枝をいくつか選び出し、全ての点について
その点につながる枝のどれかは選ばれているようにする。
選ばれる枝数はできるだけ少なくする。

最小切断
点集合を２つに分け、その間をまたぐ枝数をできるだけ少なくする。
P問題。
最大切断
点集合を２つに分け、その間をまたぐ枝数をできるだけ多くする。
NP完全問題。
平面グラフの限定すればP問題。
- 最大流・最小切断定理。

グラフの次数に着目。
点 $v\in V$ について、 $d(v)$ は、 $v$ に接続する枝の数。
グラフの次数は、各点の次数の最大値。
Vertex Cover、Hamilton circuitなどは、次数2以下のグラフについてはP問題。それを超えるとNP完全。

数系のNP完全問題
- PARTITION
  入力：n個の整数。
  出力：入力を2分割して、それぞれの和を等しくできるか否か。
  - 困難さ
    分割の仕方は $2^{n-1}$ 。
    整数の大きさに制限がない。

11/27は休講

計算量理論 のバックアップ(No.6)

計算量理論(Computational Complexity) †

内容 †

計算量理論のバックアップ(No.6)