NPの非決定性は正確に何ですか？

Question

私はNP完全性を研究しており、NP問題の定義について質問があります。材質は

非決定性は、溶液は、（1）時間ここ

Oにおける多項式多くのオプションの を推測することができるという事実を指し言う

、それはpolynomially many options in O(1) timeによって何を意味するのでしょうか？

たとえば、有名な3SATの問題の場合、指数関数的に多くのオプションはありませんか？
（各リテラルがtrue又はfalseすることができ、リテラルがn個されている場合、オプションの総数は2*2*2* ... * 2 = 2^nある紀元前）

しかし、3SAT問題はNP問題であると言います。 exponentionally多くの証明書があるにもかかわらず、どのようにNPの問題になることができますか？ n個の可能性がある - （1）引用はそれをフレージングの奇妙な方法のようですが、それは1とn Oでの間の乱数を選択することができることに似たものを参照してください可能性があることを

おかげ

Answer 1

しかし、そのうちの1つを選ぶだけでO（1）が必要です。

も参照してください。nondeterministic algorithms

"非決定論的多項式時間"はNP - "多項式時間"の完全な定義であり、重要です - 理論的に解決できるものにつながる多項式時間では、すべてのステップで正しい選択をすることができ、またはすべてのオプションを同時に実行することができます。

高さp（n）のk-aryツリーを描く。ルートから各ステップで正しい子供を（無作為に）選ぶか、何とかすべてのパスを同時に訪れることができるならば、O（p（n））の正しいリーフに到達することができます。

実際には、ランダムな選択をすることに頼ることはもちろん、無限に多くのプロセッサを持つこともできません。すべてのノードを順番に訪れるならば、O（k ^p（n） ）。

---

3SATのために、私たちはランダムにすべての私たちのランダム選択が正しかった場合、正しい結果を生成する多項式時間アルゴリズムに私たちをリードしている、すべてのリテラルのための真または偽選ぶことができます。