algorithm - 計算複雑性理論の説明

Question

数学のバックグラウンドがあると仮定して、計算複雑性理論の一般的な概要を素朴な人にどのように説明しますか?

P = NP の質問の説明を探しています。Pとは？NPとは？NPハードとは？

ウィキペディアは、読者が関連するすべての概念をすでに理解しているかのように書かれていることがあります。

score 61 · Accepted Answer

ふぅ、博士課程のフラッシュバック。よし、これだ。

まず、アルゴリズムが常に「はい」または「いいえ」で答えることができる問題である決定問題のアイデアから始めます。また、決定論的モデルと非決定的モデルという 2 つのコンピューターモデル (実際にはチューリングマシン) のアイデアも必要です。決定論的コンピューターは、私たちが常に考えている通常のコンピューターです。非決定論的コンピューターとは、無限の並列性があることを除いて、私たちが慣れ親しんでいるものと同じです。そのため、ブランチに来るたびに、新しい「プロセス」を生成し、両側を調べます。Yogi Berraが言ったように、道の分岐点に来たら、それを取るべきです.

その答えを得るための既知の多項式時間アルゴリズムがある場合、決定問題は P にあります。非決定論的マシンが答えを得るための既知の多項式時間アルゴリズムがある場合、決定問題は NP にあります。

P に存在することが知られている問題は、NP にあるのは自明です --- 非決定論的マシンは、別のプロセスを fork するために自分自身を悩ませることは決してなく、決定論的マシンのように振る舞います。PにもNPにもないことが知られている問題があります。簡単な例は、長さ n のすべてのビットベクトルを列挙することです。^{いずれにせよ、それには 2 n}ステップかかります。

(厳密には、ノードターミニスティックなマシンがポリ時間で答えに到達でき、決定論的なマシンがポリ時間で解が正しいことを検証できる場合、決定問題は NP にあります。)

しかし、ポリ時間決定論的アルゴリズムが知られていない NP に存在することが知られている問題がいくつかあります。つまり、それらが NP にあることはわかっていますが、P にあるかどうかはわかりません。従来の例は、巡回セールスマン問題 (decision-TSP) の決定問題バージョンです。都市と距離が与えられると、すべての都市をカバーし、 x未満の距離で出発点に戻るルートはありますか? 非決定論的な巡回セールスマンは分岐点に来るたびに、それを受け入れます。彼のクローンは、まだ訪れていない次の都市に向かい、最後にメモを比較して、どのクローンもx距離未満でした。

（その後、指数関数的に多くのクローンが、どのクローンを殺さなければならないかを争うようになります。）

決定 TSP が P にあるかどうかは不明です。既知のポリタイムソリューションはありませんが、そのようなソリューションが存在しないという証拠はありません。

ここで、もう 1 つの概念: 決定問題 P と Q が与えられた場合、アルゴリズムが P の解を Q の解に多項式時間で変換できる場合、Q は P に多時間可約(または単に可約) であると言われます。

(1) NP であり、(2) NP 完全であることが既に知られている問題にポリ時間還元可能であることを証明できる場合、その問題は NP 完全です。(その難しい部分は、NP 完全問題の最初の例を提供することでした。これは、クックの定理でスティーブクックによって行われました。)

つまり、誰かが 1 つの NP 完全問題のポリタイムソリューションを見つけた場合、すべての NP 完全問題に対して自動的に 1 つを得たことになるということです。これは、P=NP も意味します。

問題が NP 困難であるのは、それが NP 完全問題と「少なくとも同程度」の困難である場合に限られます。最短ルートを見つける従来型の巡回セールスマン問題は NP 困難であり、厳密には NP 完全ではありません。

score 5 · Accepted Answer

Michael Sipserの計算理論入門は素晴らしい本であり、非常に読みやすいものです。もう1つの優れたリソースは、ScottAaronsonの理論計算機科学コースの優れたアイデアです。

使用される形式は、決定問題（「はい/いいえ」の答えの問題、たとえば「このグラフにはハミルトン閉路がありますか」）を「言語」（文字列のセット）として、答えが「はい」の入力と見なすことです。「コンピューター」（チューリングマシン）とは何かという正式な概念があり、チューリングマシンでその問題を決定するための多項式時間アルゴリズム（入力文字列、たとえば「はい」または「いいえ」が与えられた場合）がある場合、問題はPにあります。

問題は、多項式時間でチェック可能である場合、つまり、答えが「はい」の入力に対して、答えが多項式時間で「はい」であることをチェックできる（多項式サイズの）証明書がある場合、NPにあります。[たとえば、証明書としてハミルトン閉路が与えられた場合、それが1つであることを明らかに確認できます。]

その証明書を見つける方法については何も述べていません。もちろん、「可能なすべての証明書」を試すことはできますが、それには指数関数的な時間がかかる可能性があります。はいまたはいいえを決定するために、常に多項式時間以上かかる必要があるかどうかは明らかではありません。これはP対NP予想です。

問題を解決できるということは、NPのすべての問題を解決できるということである場合、問題はNP困難です。

この質問も参照してください：コンピュータサイエンスにおけるNP完全とは何ですか？

しかし実際には、これらはすべておそらくあなたには漠然としているだけです。時間をかけて、たとえばシプサの本を読む価値があります。それは美しい理論です。

score 5 · Accepted Answer

これはチャーリーの投稿に対するコメントです。

(1) NP であり、(2) NP 完全であることが既に知られている問題にポリ時間還元可能であることを証明できる場合、その問題は NP 完全です。

2 番目の条件には微妙なエラーがあります。実際、証明する必要があるのは、既知の NP 完全問題 (たとえばY ) が多項式時間でこの問題 (問題Xと呼びましょう) に還元可能であることです。

このような証明方法の背後にある理由は、もし NP 完全問題をこの問題に還元でき、何とかこの問題をポリタイムで解決できれば、 NPのポリタイム解を見つけることにも成功したことになるということです。これは (不可能ではないにしても) 驚くべきことであり、それ以来、長年にわたるP = NP問題の解決に成功することになります。

この証明を見る別の方法は、反陽性証明技法を使用していると考えることです。これは、基本的に、Y --> Xの場合、~X --> ~Yであると述べています。つまり、Yを多項式時間で解けないということは、X も多項式時間で解けないということです。一方、X をポリタイムで解くことができれば、Y もポリタイムで解くことができます。さらに、推移性によって、ポリ時間で Y に還元されるすべての問題を解決できます。

上記の説明が十分に明確であることを願っています。良い情報源は、Kleinberg と Tardos によるAlgorithm Designの第 8 章、または Cormen らの第 34 章です。

score 4 · Accepted Answer

残念ながら、私が知っている最高の2冊の本（GareyとJohnson、HopcroftとUllman）は、どちらも大学院の証明指向の数学のレベルから始まります。問題全体が非常に誤解されたり、誤解されやすいため、これはほぼ確実に必要です。ジェフは、あまりにも民俗的/冗談っぽい口調で問題にアプローチしようとしたとき、耳をかみ砕かれそうになりました。

おそらく最良の方法は、多くの例と演習を使用して、big-O表記で多くの実践的な作業を行うことです。この回答も参照してください。ただし、これはまったく同じではないことに注意してください。個々のアルゴリズムは漸近線で記述できますが、問題が特定の複雑さであると言うことは、そのためのすべての可能なアルゴリズムについてのステートメントです。これが証明がとても複雑な理由です！

score 2 · Accepted Answer

Papadimitriou の "Computational Complexity" (名前のつづりが正しかったといいのですが) は良書として覚えています。

score 1 · Accepted Answer

この件に関するいくつかのリンクを次に示します。

セットのカーディナリティ、つまりセット内の要素の数に精通している場合、P は整数のカーディナリティを表し、NP は謎です: 同じか、それよりも大きいかのような質問を見ることができます。すべての実数のカーディナリティ?

score 1 · Accepted Answer

非常に単純化: 問題を解決する唯一の方法が、すべての可能な回答を列挙し、それぞれをチェックすることである場合、その問題は NP 困難です。

score 0 · Accepted Answer

私の簡単な答えは次のようになります。「計算の複雑さは、要素を追加すると問題がどれほど難しくなるかを分析することです。」

その文では、「より難しい」という言葉は、処理時間またはメモリ使用量のいずれかを指す可能性があるため、意図的にあいまいになっています。

score 0 · Accepted Answer

コンピュータサイエンスでは、問題を解決できるだけでは十分ではありません。妥当な時間内に解決できる必要があります。したがって、純粋数学では方程式を考え出すのに対し、CS ではその方程式を改良して、合理的な時間内に問題を解決できるようにする必要があります。

これは私が考えることができる最も簡単な方法ですが、あなたの目的には単純すぎるかもしれません.

score 0 · Accepted Answer

時間にもよりますが、DFA と NDFA から始めて、それらが同等であることを示すのが最善でしょう。次に、彼らは ND と D を理解し、良い副作用として正規表現をよりよく理解するようになります。

algorithm - 計算複雑性理論の説明

10 に答える 10

Related

Reference