DAA-P＆NPクラス
コンピュータサイエンスでは、目的がいくつかの値を最大化または最小化することである場合に多くの問題が解決されますが、他の問題では、解決策があるかどうかを見つけようとします。したがって、問題は次のように分類できます。
最適化問題
最適化問題とは、いくつかの値を最大化または最小化することを目的とする問題です。例えば、
特定のグラフに色を付けるために必要な最小色数を見つける。
グラフ内の2つの頂点間の最短経路を見つける。
決定問題
答えが「はい」または「いいえ」である多くの問題があります。これらのタイプの問題は、 decision problems。例えば、
特定のグラフを4色のみで色付けできるかどうか。
グラフでハミルトン閉路を見つけることは決定問題ではありませんが、グラフをチェックすることはハミルトンであるかどうかは決定問題です。
言語とは何ですか？
すべての決定問題には、「はい」または「いいえ」の2つの答えしかありません。したがって、特定の入力に対して「はい」と答える場合、決定問題は言語に属する可能性があります。言語は、答えが「はい」である入力の全体です。前の章で説明したアルゴリズムのほとんどはpolynomial time algorithms。
入力サイズの場合 n、アルゴリズムの最悪の場合の時間計算量が O(nk)、 どこ k は定数、アルゴリズムは多項式時間アルゴリズムです。
行列の連鎖乗積、単一ソースの最短パス、すべてのペアの最短パス、最小スパニングツリーなどのアルゴリズムは、多項式時間で実行されます。ただし、巡回セールスマン、最適なグラフ彩色、ハミルトン閉路、グラフ内の最長パスの検索、多項式時間アルゴリズムが不明なブール式の充足など、多くの問題があります。これらの問題は、と呼ばれる興味深いクラスの問題に属しています。NP-Complete ステータスが不明な問題。
これに関連して、問題を次のように分類できます。
Pクラス
クラスPは、多項式時間で解ける問題で構成されています。つまり、これらの問題は時間で解くことができます。 O(nk) 最悪の場合、 k は一定です。
これらの問題は tractable、他の人が呼ばれている間 intractable or superpolynomial。
正式には、多項式が存在する場合、アルゴリズムは多項式時間アルゴリズムです。 p(n) アルゴリズムがサイズの任意のインスタンスを解決できるように n 一度に O(p(n))。
必要な問題 Ω(n50) 解決する時間は、大規模な場合は本質的に手に負えません n。最もよく知られている多項式時間アルゴリズムは時間内に実行されますO(nk) のかなり低い値の場合 k。
多項式時間アルゴリズムのクラスを検討することの利点は、すべてが合理的であることです。 deterministic single processor model of computation 最大で多項式slow-dを使用して相互にシミュレートできます
NPクラス
クラスNPは、多項式時間で検証可能な問題で構成されます。NPは、少し余分な情報を使用して、主張された回答の正しさを簡単に確認できる決定問題のクラスです。したがって、私たちは解決策を見つける方法を求めているのではなく、主張されている解決策が本当に正しいことを確認するだけです。
このクラスのすべての問題は、徹底的な検索を使用して指数関数的に解決できます。
P対NP
決定論的多項式時間アルゴリズムによって解決可能なすべての決定問題は、多項式時間非決定論的アルゴリズムによっても解決可能です。
Pのすべての問題は多項式時間アルゴリズムで解決できますが、NP-Pのすべての問題は手に負えません。
かどうかは不明です P = NP。しかし、NPには多くの問題が知られており、それらがPに属している場合、P = NPであることが証明できます。
場合 P ≠ NP、PにもNP完全でもないNPに問題があります。
問題はクラスに属します P問題の解決策を見つけるのが簡単な場合。問題はに属しますNP、見つけるのが非常に面倒だったかもしれない解決策をチェックするのが簡単なら。