確定的vs. 非決定的計算

クラス P および NP を理解するには、最初に計算モデルを知っておく必要があります。したがって、この章では、2つの重要な計算モデルについて説明します。

決定論的計算とクラスP

これらのモデルの1つは、決定論的な1テープチューリングマシンです。このマシンは、有限状態制御、読み取り/書き込みヘッド、および無限シーケンスの双方向テープで構成されています。

以下は、決定論的な1テープチューリングマシンの概略図です。

決定論的なチューリングマシンのプログラムは、次の情報を指定します-

アルゴリズム分析では、決定論的な1つのテープチューリングマシンによって多項式時間で問題を解決できる場合、問題はPクラスに属します。

計算問題を解決するための別のモデルは、非決定性チューリングマシン（NDTM）です。 NDTMの構造はDTMに似ていますが、ここでは推測モジュールと呼ばれる1つの追加モジュールがあり、1つの書き込み専用ヘッドに関連付けられています。

以下は概略図です。

問題が非決定的チューリングマシンによって多項式時間で解ける場合、問題はNPクラスに属します。