講義日程-2007年度冬学期
- 計算量理論(Computational Complexity)
- 担当：今井 浩 教授
- 1.5単位
- 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)を∧で連ねた形に標準化されたもの。
うまく論理変数の値を選んだとき、論理式全体を真にできるとき、その論理式は充足可能。
どの組み合わせを選んでも真にできないとき、恒偽、充足不可能と呼ぶ。
- この充足可能正門第
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
