なぜ相対化は障壁なのですか？

Question

私が持っているオラクルが存在するというベイカーギルソロバイの証拠を説明していたとき、$ mathsf {p} = mathsf {np} $、および$ mathsf {p}を持つことができる神託 neq mathsf {np} $友人に、そのような手法が$ mathsf {p} neq mathsf {np} $の問題を証明するのに適していない理由について質問が出てきました。満足のいく答え。

より具体的に言えば、$ mathsf {p} neq mathsf {np} $を証明するアプローチがある場合、上記のような状況を起こすためにオラクルを構築できるのなら、なぜ私の方法を無効にするのですか？

このトピックに関する説明/考えはありますか？

Answer 1

より具体的に言えば、p≠npを証明するアプローチがあり、上記のような状況を起こすためにオラクルを構築できる場合、なぜ私の方法を無効にするのですか？

ベイカー、ギル、ソロベイはすでにそのような神託を建設しているため、後者の「if」は条件ではないことに注意してください。 （1）p = npと比較して神託が存在し、（2）p≠npに比べて神託が存在するということは、数学的な真実です。

これは、p≠npと同じ証明を証明するアプローチがある場合、等しくより強い結果を証明することを意味します。^a≠NP^a すべてのオラクルのために a、」それから、あなたのアプローチは矛盾するので失敗する運命にあります（1）。

言い換えれば、後者の証明は対角線化を使用しており、相対的な世界に等しく適用できるため、P≠NPの証明と時間階層定理などの証明にはいくつかの根本的な違いがあります。

もちろん、これはp≠npの証拠がないという意味ではありません。このような証拠（存在する場合）は、上記のより強い結果を証明しなければなりません。言い換えれば、証明の一部は、非相関の世界をarbitrary意的な相対的な世界と区別しなければなりません。

Answer 2

すでに良い答えがありますが、いくつかの小さなポイントを追加したいと思います。

問題を解決する手法があると仮定します。 対角線化. 。技術が特定の問題を解決できないことを示したいと仮定します。 $ mathsf {p} $ vs. $ mathsf {np} $. 。どうすればこれを表示できますか？

さらに進む前に、斜めのような手法はここでは正式な概念ではないことに注意してください（ただし、そうすることはできますが）。さらに、この手法で問題を解決できないという事実は、問題を解決するのに役立ちないという意味ではなく、それを変更したり、他の手法と組み合わせて問題を解決できるようになる可能性があります。

それでは、質問に戻りましょう。技術が特定の問題を解決できないことを示す1つの方法は、それが別の質問を解決するための異なるフレームワークでも機能することを示すことであり、その場合に得られる答えが間違っていることを示すことです。これがここで起こることです。対角線化が$ mathsf {np} $を$ mathsf {p} $から分離できる場合、同じ引数を使用して、$ mathsf {np^a} $を$ mathsf {p^a} $から分離することができます。 $ a $。しかし、これが偽であるような神託があることを知っています（$ mathsf {psace} $ - 完全な問題をOracleとして取得します）。したがって、対角線化は$ mathsf {np} $を$ mathsf {p} $から分離することはできません。

この議論の本質的なポイントは一種です 転送原則:

TMSの対角線化引数をOracleなしでTMSのOraclesでTMSに転送することができます。

これはここで可能です。これは、対角線化の議論がに基づいているためです シミュレーション さらに、シミュレーションはマシンの内部に依存するのではなく、これらのシミュレーションからの最終回答にのみ依存します。この種の対角線化は、と呼ばれます 単純な対角線化. 。シミュレーションでは、マシンがどのように機能するかは関係ありません。マシンの最終的な答えのみを気にします。 Oracleを追加してもこれは変更されないため、シミュレーションと引数は、Oraclesがあるフレームワークでも機能します。

より正式には、斜めのマシン（たとえば$ mathsf {p} $など）の関数として、マシンが問題を解決できないことを示すインスタンス（たとえば、$ sat $）までの関数と考えることができます。このカウンターエクサム機能は、対角線化関数です。対角線化は、それが与えるカウンター検例が機械の内部に依存しない場合、つまり、2つの多項式時間DTMが同じ言語を持っている場合、対角線化関数によって与えられた$ sat $を解くことができないことを示す反例は同じです。

これが大きな制限かどうか疑問に思うかもしれません。なぜ反例はマシンの内部構造に依存する必要があるのでしょうか？単純な対角線化を使用して証明できない対角線化を使用して分離を証明できますか？答えはイエスです。実際、Kozenは1978年の論文「サブリカューリブクラスの索引付け」（BGSの結果の3年後）で、$ mathsf {np} $を$ mathsf {p} $から分離できる場合、一般的な対角線化引数があります。 。そして実際には、そのような議論が発見されています。たとえば、Fortnowとvan MelkebeekのSAT（2000）の時空間の下限を使用する 間接的な対角線化 それは非simple的な対角線化を与えます。

それで、対角線化は$ mathsf {p} $ vs. $ mathsf {np} $を解くことができないという主張はありませんか？まあ、一般的に、ここでの対角線化によって専門家が意味するものは 単純な対角線化 そして、それには正当な理由があります。

一般的な斜めの議論は非常に一般的であるため、テクニックと呼ぶことはあまり意味がありません。あらゆる洞察なしに、分離の引数を斜めの議論に簡単に変えることができます。小さなクラスではなく、より大きなクラスで関数を選択できます。小さなクラスのマシンの列挙を列挙します。 $ m $を列挙内の任意のマシンとします。 $ m $の反例を定義する必要があります。しかし、私たちはすでに$ m $が問題を解決できないことを知っているので、そこに 存在します これを示すインスタンスは、$ m $の対角線化関数の値をそのインスタンスに定義します。詳細を確認したい場合は、これが大きな絵画のビューです。

夏：

• 専門家が「対角線化は$ mathsf {p} $ vs. $ mathsf {np} $を解くことができない」と言うとき、それらが意味するもの」単純 対角線化は$ mathsf {p} $ vs. $ mathsf {np} $ "一般的なものではありません。
• 単純な対角線化が$ mathsf {np} $を$ mathsf {p} $から分離できない理由は、それが神託でフレームワークに転送されるためです（文献では「斜めの相対化」と述べられており、分離はそこに保持されません。 。
• OracleのないフレームワークからOracles Worksを使用してフレームワークへのこの転送は、単純な対角線がTMSのブラックボックスシミュレーションに基づいており、Oracleがあるかどうかにかかわらず、マシンがどのように機能するかは関係ありません。

対角線化についてもっと学ぶための2つの良い論文はそうです

• ランスフォートノーの調査ペーパー「斜め化」、2001年、および
• Russell Impagliazzo、Valentine Kabanets、Antonina Kolokolovaの論文「代数への公理的アプローチ」、2009年 代数化 の拡張です 単純な対角線化.)

Answer 3

$ mathrm {a} $ and $ mathrm {b} $を2つの複雑なクラスとします。分離（$ mathrm {a} neq mathrm {b} $）またはcollapse（$ mathrm {a} = mathrm {b} $）は、すべての口頭で$ mathrm {o} $ $の場合に相対化すると言われています。 $ mathrm {a}^ mathrm {o} neq mathrm {b}^ mathrm {o} $または$ mathrm {a}^ mathrm {o} = mathrm {b}^ mathrmmrmm {o} $それぞれ。 Baker-Gill-Solovayの証拠は、$ p = np $または$ p neq np $が相対的ではないことを示しています。

なぜこれが問題なのですか？この証拠が発表されたとき、私たちが知っていたテクニックとトリックの大部分は、「相対化された」複雑さのクラスを分離または崩壊させることを知っていました。たとえば、タイム階層定理（およびそれの空間と非決定論的バージョン）「相対化」：それらは、この分離が相対的になるクラスの分離を証明し、実際には、分離が点在するより強い結果を証明することを証明します。任意のオラクル。

Oracleが存在するかどうかに関係なくテクニックまたはトリックが機能する場合、上記の引数で$ p = np $または$ p neq np $を証明することはできません。これは、私たちが知っている多くのトリックとテクニックがこの問題に取り組んでいないことを意味します（または実際に多くの未解決の問題について）。また、$ p neq np $ proofとされる任意の正気チェックとして使用することもできます。間違っている。