NPクラスの複雑さ

Question

P問題は、問題を解決するために必要なアルゴリズムが多項式またはそれ以下の時間で実行できるため、NP問題は多項式アルゴリズムが存在しないという問題です。

基本的に、多項式以上のアルゴリズムの複雑さをNPとみなすすべての問題がありますか？

P = NPは基本的に「多項式時間よりも長いアルゴリズムを使って問題を解決する方法はありますが、今回は多項式時間で解くのですか？

Answer 1

これは間違っています。適切な定義をするには、googleを使用してください。簡単な説明のために：

NPは「非決定論的多項式時間」を意味する「非多項式時間」を表しません。おおまかに言えば、多項式時間で解を見つけることはできないかもしれませんが、解が多項式時間で検証できるということです。一例はグラフの色付けです。グラフと色付けが与えられている場合は、多項式時間に色分けが適切かどうかを確認することが簡単です（つまり、各辺を見て色が異なるかどうかを確認する）。しかし、P！= NPならば、多項式時間に着色を見つけること、または着色が存在するかどうかを判断することは不可能である。なぜなら、グラフの着色はNP困難であるからである。

したがってP=NPは、解が多項式時間で検証できる問題があれば、多項式時間で解を見つけることもできます（大まかにかつ非公式）。

注：私が言ったように、これは簡単で非公式の説明です。技術的には、PとNPだけが決定問題に適用されるので、はい/いいえの問題はどちらかのクラスに属することができます（例えば、着色が存在するかどうかの判定はNPでは問題ですが、色付けを見つけることは決定ではない問題）。