相対化の背後にある直観

Question

私は計算の複雑さについてコースを取ります。私の問題は私が理解していないことです 相対化方法. 。残念ながら、多くの教科書で少しの直感を見つけようとしましたが、これまでのところ成功しませんでした。誰かがこのトピックに光を当てて、私が自分で続けることができるようになったら感謝します。次の文章はほとんどありませんが、相対化についての私の考えは、議論をナビゲートするのに役立ちます。

非常に多くの場合、相対化は対角線化と比較して生まれます。これは、可算セットとカウントのないセットを区別するのに役立つ方法です。どういうわけか、$ p $ vs $ np $の質問は対角線化によって解決できないという相対論から来ています。なぜ相対化が対角線化の役に立たないことを示す理由と、それが実際に役に立たない理由が役に立たない場合、私は本当に考えていません。

Oracle Turing Machine $ M^a $の背後にあるアイデアは非常に明確です。ただし、$ np^a $と$ p^a $に関しては、直感が消えます。 Oracleは特別な言語用に設計されたブラックボックスであり、Oracleの入力の文字列が時間1に言語にあるかどうかという質問に答えます。私が理解したように、Oracleを含むTMは、補助操作を行い、Oracleに尋ねることです。したがって、TMのコアはOracleであり、他のすべてはそれほど重要ではありません。 $ p^a $と$ np^a $の違いは何ですか。それらの両方のOracleは時間1で機能すると考えさえしました。

最後のことは、$ p^b neq np^b $のようなオラクル$ b $の存在を証明することです。私はいくつかの教科書で証拠を見つけました、そして、それらのすべてで証明は非常に曖昧に思えます。使ってみました Sipserによる「複雑さの紹介」、第9章。難治性, 、そして、すべての多項式時間Oracle TMS $ M_I $のリストの構築のアイデアを取得しませんでした。

これは多かれ少なかれ、私が相対化について知っていることはすべてです。誰かがトピックについて彼/彼女の考えを共有することを決定したかどうかを感謝します。

補遺: ：教科書の1つで、$ np^b $言語の例を見つけました（計算の複雑さ：Boaz Barak Sanjeev Aroraによる最新のアプローチ。Theorem3.7。Page74）。 $ u_b = left {1^n：Some Space String Space Space and Space n Spaceは space b right } $ unary言語です。 （1,11,111,1111、...）はすべて$ U_B $にあると思います。著者は、そのような言語は$ np^b $であると断言します。これは理由がわかりません。したがって、bのOracleは時間のすべてを解決できます。なぜOracleで非決定的TMが必要なのか。 $ np^b $の良い例ではない場合は、$ np^b $の存在を承認するようにしてください。

Answer 1

あなたは本当に質問をしていませんが、$ rm {p}^a $が何を意味し、$ rm {np}^a $は言語$ a $を意味するものを知らないようです。クラス$ rm {np}^a $は、$ a $のチューリングマシンをOracleとして与えられて、「NP Time」で決定できるすべての言語です。これは、多項式時間で実行される$ A $にアクセスできる非決定的なチューリングマシンを意味します。 $ rm {p}^a $は決定論的バージョンです。