計算量理論

体系立てては書けないので，あくまでメモ。思い出しながら書いてるから間違いも多いハズ。厳密な定義は教科書読んでね。

時間計算量:Time Complexity

多項式時間(polynomial time)：入力文字列の長さ n に対して， $15n^5 + \sqrt[3]{26}n^2 - 3$ とかの多項式で表すことができる計算ステップ数
指数時間(exponential time)：入力文字列の長さ n に対して， $2^{(n^\rho)}$ とかの指数式で表すことが出来る計算ステップ数
入力文字列の長さに対してってのは以下略。

$P = \bigcup_k TIME(n^k)$

任意の言語 A に対する verifier は，次に示す V というアルゴリズムである。

$A = \{ w | V \mbox{ accepts } \langle w,c \rangle\ \mbox{ for some string } c \}$

この verifier を持つ言語で，それが多項式時間で動作する。 $\Leftrightarrow$ その言語は CLASS NP に属す。

つまり，検証したい文字列 w とある文字列 c を読み込んで， $w \in A$ かどうか判定する非決定性チューリングマシン
ある文字列 c とは，つまり検証したい文字列が A に含まれるかどうか判定するために必要な情報のこと。certificate とか proof って呼ばれる。
- 答えのリストそのものかもしれないし，CFLかもしれない。
- 重要なのは，非決定性チューリングマシンが多項式時間で判定可能ってこと。
polynomial time verifier は w の長さに対して多項式時間で判定する機械 $\Leftrightarrow$ c の長さは w の長さに関する多項式
- そもそも verifier が多項式時間で動くわけだから，ステップ数を超えた長さの文字列は読み込めない
にしてもWikipedia日本語版だと凄く短い説明なのね…
NP とは nondeterministifc polynomial time の略¹⁾らしい