NP問題（NP）とは
NP / Nondeterministic Polynomial Time
非決定性チューリング機械が多項式時間で解け、与えられた解の正しさも多項式時間で検証できる決定問題の集合
概要
NP問題(クラスNP)とは、非決定性チューリング機械上で多項式時間内に解ける決定問題全体の集合。実用的には、ある解の候補が与えられたとき、それが正しい解であるかを多項式時間で検証できる問題のクラスとして理解される。 巡回セールスマン問題の判定版、充足可能性問題(SAT)、部分和問題などがNPに属する代表例。 NPに属する問題の中でも、NP内の全ての問題を多項式時間で還元できる最も難しい問題群を「NP完全」と呼び、SATはNP完全性が最初に証明された問題として知られる。 P⊆NPは自明に成り立つが、NPに属する問題が全て多項式時間で解けるか(P=NP)は未解決の問題。
歴史
1971年、Stephen CookがNP完全性の概念とSATがNP完全であることを示した論文「The Complexity of Theorem Proving Procedures」を発表。同時期にLeonid Levinも独立に同様の結果を示したことから、この定理はCook-Levinの定理と呼ばれる。1972年にはRichard KarpがNP完全な21個の問題を示し、NP完全性の概念を広めた。
比較
- P問題 — NPは解の検証のみ多項式時間で可能な問題のクラス、Pは解を求めること自体が多項式時間で可能な問題のクラス