前回のおさらい

全ての整数$n >= n_0$に対してある正の整数$c$と$n_0$が存在して$f(n) <= cg(n)$. という言い回しなんか直感的じゃない気がします.

一階述語論理で書けば一見$∀n(∃c ∈ N^+(∃n_0(n >= n_0 ∧ f(n) <= cg(n))))$のように見えて, 実は$∃c ∈ N^+(∃n_0(∀n(n >= n_0 → f(n) <= cg(n))))$なんですね. 日本語の順序と論理式の順序が違うからわかりにくい.

クラスP

前回関数の計算時間を分類する方法を学んだ.

動作時間が多項式時間は計算可能, 指数時間は計算困難.

多項式は$n, n^2, n^3, …$のように, $n^a$で$a$は定数のようなもの.

指数関数は$2^n, 3^n, …$のようなもの.

階乗はStirlingの公式より$n! ≒ \sqrt{2πn}\frac{n}{e}^n$なので指数関数より速く増加する.

クラスPを(決定戦単一テープ)Turing機械によって多項式時間で判定できる言語のクラスとする.

アルゴリズムの計算量をオーダーで評価する場合, 計算モデルを気にしなくて良い. オーダーの議論では計算モデルは気にしない.

質問しました. ｢今のコンピュータって, チューリングマシンで言うテープに, メモリとしてランダムアクセスできますよね, これってステップ数の削減にはなりませんか?｣ ｢ステップ数は削減できるかもしれないけれど定数倍だからオーダーには影響しません｣ なるほど.

有向グラフ$G$において節点$S$から別の節点$T$にたどり着く経路(PATH)が存在するかどうかを判定する問題は総当りすると節点の個数$m$に対して指数時間かかる. しかし適切なアルゴリズムを使えば多項式時間になる.

有向グラフにおいて与えられた2つの節点を繋ぐHamilton路が存在するか判定する問題(HAMPATH)は, 多項式時間のアルゴリズムが発見されていないため, 指数時間のクラスNPに属する.

クラスNP

クラスNPは多項式時間で検証が可能なクラス.

検証が可能というのは答えをもらった時に答えが正しいか判定すること.

実用的に重要な問題が多く含まれる.

非決定性Turing機械を用いて多項式時間で判定できるクラスと等しい.

クラスPとNP

• クラスP: 多項式時間で判定が可能(解ける)な問題のクラス
• クラスNP: 多項式時間で検証が可能な問題のクラス

課題

非決定性チューリングマシンとは何か. 12月20日まで.