NPとはnondeterministic polynomial（非決定性多項式）の略で、NP問題とは計算理論においてあるむずかしさのクラスの（解くのに時間がかかる）問題を指す。NP完全問題とは、NP問題の中でもむずかしいあるクラスの問題を指す。NP完全問題はコンピューターで多項式時間では解けない（待ち時間内に答えが得られない）と考えられている。世の中の重要な問題のほとんどがNP完全問題であることがわかっている。