NP完全（エヌピーかんぜん）とは、計算理論における問題のクラスの一つで、非決定性チューリングマシン（Nondeterministic Turing machine）によって多項式時間で解くことができる（NP）問題の中でも、特に難しい問題群を指します。これらの問題は、一つが多項式時間で解けるようになれば、他のNP問題もすべて多項式時間で解けるようになるという性質を持っています。この性質を「NP困難（NP-hard）」といい、NP完全はNPに属しつつNP困難である問題のことを言います。
では、NP完全についてもう少し詳しく見ていきましょう。
まず、「多項式時間」とは、問題のサイズに対して、その解を得るのに必要な時間が問題のサイズの多項式で表せることを意味します。たとえば、問題のサイズをnとしたとき、計算時間がn^2やn^3で表せるアルゴリズムは多項式時間アルゴリズムです。一方で、2^nのように指数関数的に時間が増加するアルゴリズムは非多項式時間アルゴリズムと言われます。
NP問題とは、「Non-deterministic Polynomial time」の略で、非決定性チューリングマシンが多項式時間で解くことができる問題の集合です。直感的には、「答えが与えられたときに、それが正しいかどうかを多項式時間で確認できる問題」と考えることができます。
NP完全問題は、NP問題の中でも特に難しいとされる問題で、他のどのNP問題よりも解くのが難しいとされています。そして、もしNP完全問題の一つが多項式時間で解けるアルゴリズムが見つかれば、NPに属するすべての問題が多項式時間で解けることになります。これは、計算理論における大きな未解決問題である「P=NP問題」と深く関連しています。Pは決定性チューリングマシンで多項式時間で解ける問題のクラスを指し、P=NP問題は、PとNPが等しいかどうか、つまり、すべてのNP問題が多項式時間で解けるかどうかを問うものです。
NP完全問題の例としては、以下のようなものがあります。
- 巡回セールスマン問題（Traveling Salesman Problem, TSP）：複数の都市を巡り、最短の経路で元の都市に戻るルートを見つける問題。
- クリーク問題（Clique Problem）：ネットワーク内で、全員が互いに知り合いである最大のグループ（クリーク）を見つける問題。
- 頂点被覆問題（Vertex Cover Problem）：グラフの全ての辺が少なくとも一方の端点によってカバーされる最小の頂点集合を見つける問題。
これらの問題は、それぞれがNP完全であることが証明されており、現在に至るまで多項式時間で解くアルゴリズムは見つかっていません。したがって、これらの問題を効率的に解くためには、近似アルゴリズムやヒューリスティックな手法が用いられることが多いです。
NP完全問題は、コンピュータサイエンスだけでなく、経済学、生物学、工学など多くの分野で現れるため、その解法には幅広い関心が寄せられています。もしP=NPが証明されれば、これらの分野における多くの問題が劇的に解決される可能性がありますが、多くの専門家はP≠NPであると考えており、その証明には至っていません。
