NP
#計算量理論
#Algorithm
#NP-hard
#NP-complete
Non-deterministic Polynomial time
非決定性チューリングマシン
を用い
多項式時間
$ O(n^k)
で解ける問題の属するクラス
現実的な
決定性チューリングマシン
を用いると、解の存在判定に指数関数オーダーの時間時間がかかってしまう可能性がある。
ただし、補助情報としてある入力が与えられた時、それが解であるか否かの検証は決定性チューリングマシンを用いて多項式時間で可能(
多項式時間検証可能性
)。
NP問題の例
ハミルトン閉路問題
与えられたグラフのすべての点を一度ずつ通って元の点に戻る経路経路があるか?
https://gyazo.com/e391d770f2c9ce40a1a98c7d3df00cb4