algorithm - 決定論的多項式解に対する非決定的多項式解

Question

非決定的多項式ソリューションは、決定的多項式ソリューションよりも常に望ましくありませんか? 適当な理由付けをお願いします。

Answer 1

すべての決定論的多項式解は、非決定論的多項式解に変換できます [ PはNPのサブセットであるため]

逆が真かどうかはわかりません [P=NP か P!=NP かはわかりません]。したがって、P!=NP の場合、非決定論的な問題があります [すべてのNP 完全問題] 。多項式解ですが、多項式解ではありません。

したがって、決定論的多項式解を非決定論的多項式解に変換することはできますが、反対のことができるかどうかはわかりません。決定論的多項式解がある場合、実際には非決定論的多項式解もあります。

Answer 2

アミットの有益な回答の補足として、実際の入力については、NPソリューションの方が優れている場合があります。たとえば、T(n) = 2^n を持つ NP 問題の指数アルゴリズムを考えてみましょう。最良の場合の時間計算量が T(n) = (1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 、000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000待ちます 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 それは多項式ですが、おそらく指数関数の問題を解決したいと思います。

同じ問題に対して、指数関数的またはより悪い解または多項式解を使用するかどうかという質問がある場合、一般的に答えは次のとおりです。入力サイズによって異なります。漸近的な複雑度が高いアルゴリズムは、妥当なサイズのほとんどの入力に対して高速になる可能性があります。複雑さの低いアルゴリズムを使用することが理にかなっているポイントがありますが、実際には (または宇宙の存続期間中に) そのポイントに到達することは決してないかもしれません。

編集：入力の他の特性にも依存する可能性があります。たとえば、最悪の場合、マージソートはクイックソートよりも優れていることが証明されていますが、クイックソートはマージソートよりも優れている場合があります。データがクイックソートの最悪のケースになるような形式になる可能性が非常に低いことがわかっている場合は、クイックソートを試す価値があるかもしれません。