決定論的計算と非決定論的計算

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

決定論的計算とクラスP

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

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

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

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

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

以下は概略図です。

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