Turing Machine と計算量

計算量

入力の長さ n に対して、どれくらいの計算時間やメモリが要求されるかを表す方法を考える。

計算を Turing machine で行ない、その Turing machine が計算終了までに費すステップと使用したテープの長さを使う。

nの式で表す。係数は問わない。

いろんな計算量
　　 o(n) 入力に比例した計算時間

　　 o(n^2) 入力の長さの二乗の計算時間

　　 o(n * log n)

　　 o(exp n) 入力の長さの指数的な計算時間

　　 o(exp (exp n)) 入力の長さの指数的な計算時間

Turing machine ではなく、もっと高級なモデル(例えばメモリを持つもの)を考えても、計算量は同じ。

いろんな計算量
	o(n)	入力に比例した計算時間
	o(n^2)	入力の長さの二乗の計算時間
	o(n * log n)
	o(exp n)	入力の長さの指数的な計算時間
	o(exp (exp n))	入力の長さの指数的な計算時間

それは、テープの長さを考慮しても結局は係数しか違わないから。o(1) は入力を受け付ける時間を考慮してない時に意味がある。

実際には係数も問題になることが多い。

o(n)

o(n^2)

    naive append

o(n*log n)

    quick sort

o(exp n)

P

Turing machine で多項式時間がかかる計算量。

Pの例。

　　単純サーチ　　数え上げ

Non deteministic turing machine

Automaton と同じように非決定的なTuring machine (NTM)を考える。Deterministic turing machine (DTM)の遷移関数は

    tδ : Q →  Σ → Q × ( Write  Σ ) ×  Move }

だったが、

    tnδ : Q →  Σ → Q × ( Write  Σ ) ×  Move } → Bool

と複数の動作が可能となる。次のテープの状態も複数あることになる。

例えば、1からn までの素数を計算するのに DTMでは1から順番に計算していくが、NTMでは全部一度に調べることができる。

NTMで多項式時間がかかる計算量を NP という。

大雑把に言えば、NTMはCPUが無限にある並列計算機である。

NTMをDTMで simulation する。

非決定性の数が定数つまりCPUの数が固定なNTMは、DTMと定数分しか差がない。従って計算量的には同じ。

非決定性の数は入力の長さよりは使用したテープの長さに依存する。NTMでPということは、並列に動く個々のTMのテープの使用量はPで押さえられる。

選択は有限(kとする)なので、k^P の分岐が起きている可能性がある。

つまり、NP(NTMでP)な計算では指数的にCPUが使われる可能性がある。従って、一般的には NTMをDTMでsimulationするには指数的なステップがかかる。

NPの例

Boolean formula の satifiberbilty を調べる

SAT

coNPの例

Boolean formula の validity を調べる

P=NP?

NP はあまりに強力だが、EXP(指数的な計算量)では押さえられる。

NP hard

任意のNPの問題をとくことができる一般的な問題を NP complete という。

最低でもNPな計算量を要求する計算を NP hard という。NP hard は NP complete とは限らない。

P space

量化記号を含むSAT。

計算量の階層

どこの隙間も空でないことは証明されていない。