DAA-P＆NPクラス

コンピューターサイエンスでは、いくつかの値を最大化または最小化することが目的である多くの問題が解決されますが、他の問題では解決策があるかどうかを見つけようとします。したがって、問題は次のように分類することができます-

最適化の問題

最適化の問題は、目的がいくつかの値を最大化または最小化することです。例えば、

特定のグラフに色を付けるために必要な色の最小数を見つける。
グラフ内の2つの頂点間の最短経路を見つける。

決定問題

答えが「はい」または「いいえ」である多くの問題があります。これらのタイプの問題は、*決定問題*として知られています。例えば、

特定のグラフを4色のみで着色できるかどうか。
グラフでハミルトニアンサイクルを見つけることは決定問題ではありませんが、グラフをチェックすることはハミルトニアンであるかどうかは決定問題です。

言語とは？

すべての決定問題には、yesまたはnoの2つの答えしかありません。したがって、特定の入力に対して「はい」と答えた場合、決定問題は言語に属する可能性があります。言語は、答えが「はい」である入力の全体です。前の章で説明したアルゴリズムのほとんどは、*多項式時間アルゴリズム*です。

入力サイズ n の場合、アルゴリズムの最悪の時間複雑度が O（n ^ k ^） （ k は定数）の場合、アルゴリズムは多項式時間アルゴリズムです。

マトリックスチェーン乗算、単一ソース最短パス、全ペア最短パス、最小スパニングツリーなどのアルゴリズム多項式時間で実行します。ただし、巡回セールスマン、最適なグラフの色付け、ハミルトニアンサイクル、グラフ内の最長パスの検出、多項式時間アルゴリズムが不明なブール式を満たすなど、多くの問題があります。これらの問題は、 NP-Complete 問題と呼ばれる興味深い状態の問題に属し、そのステータスは不明です。

この文脈では、次のように問題を分類することができます-

Pクラス

クラスPは、多項式時間で解ける問題で構成されます。これらの問題は、 k が一定の場合、 _ O（n ^ k ^）_ を最悪の場合に時間内に解決できます。

これらの問題は tractable と呼ばれ、他の問題は intractableまたはsuperpolynomial と呼ばれます。

形式的には、アルゴリズムが時間 O（p（n）） でサイズ n の任意のインスタンスを解決できる多項式 p（n） が存在する場合、アルゴリズムは多項式時間アルゴリズムです。

解決に ＆ohm;（n ^ 50 ^） 時間を要する問題は、本質的に大きな n では扱いにくいです。ほとんどの既知の多項式時間アルゴリズムは、 _ O（n ^ k ^）' を _k' のかなり低い値で実行します。

多項式時間アルゴリズムのクラスを考慮することの利点は、すべての合理的な*決定論的な単一プロセッサ計算モデル*が、せいぜい多項式スローdで互いにシミュレートできることです。

NPクラス

クラスNPは、多項式時間で検証可能な問題で構成されます。 NPは、わずかな追加情報を使用して、主張された回答の正確性を簡単に確認できる意思決定問題のクラスです。したがって、解決策を見つける方法を求めているのではなく、申し立てられた解決策が本当に正しいことを検証するだけです。

このクラスのすべての問題は、徹底的な検索を使用して指数関数的に解決できます。

P対NP

決定論的多項式時間アルゴリズムによって解決可能なすべての決定問題は、多項式時間非決定論的アルゴリズムによっても解決可能です。

Pのすべての問題は多項式時間アルゴリズムで解決できますが、_NP-P_のすべての問題は難解です。

*_P = NP_* かどうかは不明です。 しかし、NPには、Pに属している場合、P = NPであることが証明できるという性質を持つ多くの問題が知られています。

*_P≠NP_* の場合、PにもNP-Completeにもない問題がNPにあります。

問題の解決策を見つけやすい場合、問題はクラス P に属します。問題は、非常に退屈な解決策を簡単に確認できる場合、 NP に属します。

Design-and-analysis-of-algorithms-p-np-class

目次