計算量理論

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

• 多項式時間(polynomial time)： 入力文字列の長さ n に対して，とかの多項式で表すことができる計算ステップ数
• 指数時間(exponential time)： 入力文字列の長さ n に対して，とかの指数式で表すことが出来る計算ステップ数
• 入力文字列の長さに対してってのは以下略。

• ある１テープ決定性チューリングマシンが多項式時間で決定可能な言語のクラス

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

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

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