「NP困難」の版間の差分

もし何れかのNP困難な問題を[[多項式時間]]で解くアルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることになり、P = NP が成り立つ。同様に、何れかのNP完全な問題を多項式時間で解くアルゴリズムが存在した場合も、NPに属する全ての問題が多項式時間で解ける。そのため「'''何れかの'''NP困難（またはNP完全）な問題を多項式時間で解く方法が存在するか」という問題はそのまま [[P≠NP予想]]の否定の証明になる。ところが、P＝NPが成立しても、「'''任意の'''NP困難な問題はが多項式時間で解ける」とは必ずしも言えない。これに対し、P≠NPが成り立つならば、「'''如何なる'''NP困難な問題についても、これを多項式時間で解く一般的なアルゴリズムは存在しない」と言える。この関係を右上の[[ベン図]]に示す。