Pクラス

とは

1. P ⊆ NP: Pクラスに属する問題は、多項式時間で解ける問題です。NP問題はPクラスに含まれます。なぜなら、Pクラスの問題は多項式時間で検証可能であり、そのような問題の解も多項式時間で求められるためです。

2. P = NP か否かは未解決問題: PクラスとNPクラスが完全に一致するかどうかは、計算理論の中での重要な未解決問題です。この問題については「P vs NP問題」と呼ばれ、現在のところ解決されていません。もし P = NP が証明されれば、Pクラスの問題は多項式時間で解けることが証明され、NP問題も同様に多項式時間で解けることが示されます。

3. NP完全問題: NP完全問題とは、NPクラスの中でも最も難しい問題であり、どのNP問題でも多項式時間で変換可能な問題です。つまり、NP完全問題が多項式時間で解けるならば、すべてのNP問題が多項式時間で解けることになります。したがって、もしNP完全問題の一つがPクラスに属すれば、P = NP が成り立つことになります。