[解決済み] NP - 非決定性多項式時間

質問

NPの定義を複数見てきましたが、非決定性多項式時間と呼んでいるのが少し気になります。

NPは非決定論的多項式時間で認識可能な言語の集合である。

私が理解したのは、通常のコンピュータ(ランダム性を持たない)では多項式時間で言語を認識できないが、何らかの非決定性(コインフリップ？)を持つコンピュータはそれを多項式時間で解くことができる、ということでしょうか。

どなたか訂正していただけませんか？コイン弾きで実際に問題が解決される例を教えてください。そうでなければ指数関数的になるはずです。

NPには多項式時間で検証可能な言語も含まれるという定義は理解できるのですが、非決定論を使ってどうやって認識するのかがわかりません。

どのように解決するのですか？

実際、コインフリップはランダム性の問題であり、一部の人々は 間違って 非決定性をランダム性と表現しています。例えば、次のような問題があるとしよう。

n個の扉があり、そのうちの1個の扉の奥に探したいものがある。では、さまざまなアプローチを分析してみましょう。

(説明を簡単にするために、ビッグ・オーなどの漸近的な表記は使っていないことに注意)

決定論的である。 決定論的アルゴリズムの例として、すべてのドアを左から右へ一つずつ開けるというものがある。したがって、最悪の場合の複雑さはn回の操作となる

ランダム化されている。 コインをひっくり返して、裏が出たら左から右へ、表が出たら右から左へドアをチェックするんだ。だから、期待される意味において、私はn/2の操作を得ることになる。(演習：なぜ？）そして、ランダム化アルゴリズムでは、良い平均（期待値）の振る舞いを探します。

非決定論的である。 非決定論は、現実世界ではありえない、まったく別の話です。非決定性の力があれば、複数の選択肢に直面したとき、すべての選択肢を同時に試すことができる。つまり、非決定論的アルゴリズムは、n個の扉をすべて同時に開けることができる。したがって、1回の操作で賞品を見つけることができるのである。

さて、非決定性を使って多項式に解けるものの例です。例えば、2つの扉（深さ1）に直面し、1つを選ぶと、また2つの扉（深さ2）が現れ、これが深さnまで続くとします。つまり、最後の深さには2^n個の扉があり、そのうちの1つの後ろに賞品があるとします。

決定論的アプローチで賞品を見つけるには、2^n回の演算が必要です。しかし、非決定論を用いると、深さ1の扉を2つ同時に開き、深さ2の扉を4つ同時に開く、といったことができる。つまり、n回の（非決定論的）操作の後に景品を見つけることができるのです