計算複雑性理論の説明

https://stackoverflow.com/questions/308213

08-07-2019
|

質問

数学のバックグラウンドを仮定して、計算の複雑さの理論の一般的な概要をどのように素朴に伝えますか？

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

Wikipediaは、読者が関連するすべての概念をすでに理解しているように書かれている場合があります。

解決

Hoooo、博士課程コンプのフラッシュバック。さて、ここに行きます。

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

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

Pにあることが知られている問題はNPで些細なことです---非決定性のマシンは、別のプロセスをフォークするためにトラブルを起こすことはなく、決定性のプロセスのように動作します。 PにもNPにもないことが知られている問題があります。簡単な例は、長さnのすべてのビットベクトルを列挙することです。何であれ、それは2 ⁿステップかかります。

（厳密には、非決定的マシンがポリタイムで回答に到達でき、決定論的マシンがポリタイムで解が正しいことを検証できる場合、決定問題はNPにあります。

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

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

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

もう1つの概念：決定問題PおよびQが与えられた場合、アルゴリズムが多項式時間でPの解をQの解に変換できる場合、Qは poly-time reducible と言われます（または単に還元可能）Pに。

問題は、（1）NPにあること、および（2）既にNP完了であることがわかっている問題に対して多重時間還元可能であることを証明できる場合、NP完了です。（その困難な部分は、NP完全問題の first の例を示しました。これは、クックの定理。

つまり、実際には、あるNP完結問題のポリタイムソリューションを見つけた人は、NP完結問題すべてについて自動的に解決されるということです。また、P = NPを意味します。

問題は、それが「少なくとも」と同じ場合にのみNP困難です。 NP完全問題としては難しい。最短ルートを見つけるという従来の巡回セールスマン問題は、NP完全ではなく、NP困難です。

他のヒント

Michael Sipser の計算理論の紹介は素晴らしい本であり、非常に読みやすいです。別の great リソースは、Scott Aaronsonの Greatです。理論的コンピューターサイエンスのアイデアコース。

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

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

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

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

この質問もご覧ください。コンピューターサイエンスにおけるNP完全とは何ですか

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

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

（1）NPにあることを証明できる場合、問題はNP完全です。（2）既知の問題に対して多時間還元可能であることを示す NP完全である。

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

この証明方法の背後にある理由は、 NP -完全な問題をこの問題に還元し、どういうわけかこの問題をポリタイムで解決できれば、 NP の完全な問題のポリタイムソリューションを見つける。これは、（不可能ではないにしても）驚くべきことです。それ以来、長年にわたる P = NP の問題。

この証明を見る別の方法は、それが本質的に Y-＆gt; X 、次に〜X-＆gt; 〜Y 。つまり、多項式時間で Y を解くことができないということは、ポリタイムでもXを解かないということではありません。一方、Xをポリタイムで解くことができれば、Yもポリタイムで解くことができます。さらに、推移性によって、ポリタイムでもYに減少するすべての問題を解決できます。

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

残念ながら、私が知っている最高の2冊の本（ Garey and Johnson および HopcroftとUllman ）は両方とも、卒業証書指向のレベルから始まります。数学。これはほぼ間違いなく必要です。なぜなら、問題全体が非常に簡単に誤解または誤解されるからです。ジェフ彼も問題に近づこうとしたとき、耳をほとんど噛み砕かれましたフォークシー/ジョッキーのトーン。

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

「計算の複雑さ」を覚えていますPapadimitriouから（私は正しい名前をつづりました）良い本として

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

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

セットのカーディナリティ、つまりセット内の要素の数の概念に精通している場合、NPが謎であるときに整数のカーディナリティを表すPのような質問を見ることができます。すべての実数の基数のように大きくなりますか？

単純化した答えは次のとおりです。「計算の複雑さは、要素を追加したときに問題がどれほど難しくなるかの分析です。」

その文では、単語「より難しい」処理時間またはメモリ使用量のいずれかを指す可能性があるため、意図的に曖昧です。

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

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

お持ちの期間によっては、DFA、NDFAから始めて、同等であることを示すのが最善かもしれません。その後、彼らはND対Dを理解し、素晴らしい副作用として正規表現をよりよく理解します。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow