・クラスPとは、決定性チューリング機械において、多項式時間で判定可能な(Yes/No)問題のクラスである。 ・クラスNPは、Yesとなる証拠が与えられたとき、多項式時間で検証が可能な(Yes/No)問題のクラスである。 ・クラスPとクラスNPが等しくないという予想を…