NP - Wikipedia計算複雑性理論における NP (英: Non-deterministic Polynomial time)は、複雑性クラスのひとつであり、答えがyesとなるような問いに対して、多項式時間で検証できる証拠が存在する決定問題のクラスである。 定義[編集] NP は、NTIMEを使って次のように定義される[1]。 つまり、非決定性チューリングマシンによって多項式時間で解ける決定問題のクラスであり、名称も 英: Non-deterministic Polynomial time（非決定性多項式時間）の略である。また、多項式時間検証可能という同値な定義もある。言語 が NP に属するとは、多項式時間決定性チューリングマシン と多項式 が存在し、次の性質を満たすことを言う。 ならば、ある証拠 が存在し、 ならば、どんな証拠 でも、 例[編集] ハミルトン閉路問題は、「与えられたグラフについて、全ての頂
