ランダムなオラクルを持つロジックのP対NP

ランダムなオラクル$ f: {0,1 } ^ ast を {0,1 } $に選択し、新しい記号$ g
$を追加して論理$ ZFC ^ f $を定義します。 g $は正しい型を持ち、 {0,1 } ^ ast $の各$ s
に対して1つの公理$ g(s)= f(s)$を持ちます。 $ f $は$ ZFC ^ f
$の記号ではないので、これは無限の公理の集合です。

$ g $への入力に2番目のテープを使用し、2番目のテープに$ g $の値を置くなど、標準的な方法で$ g $
-oracleチューリングマシンを定義することができますテープ。次に、複雑さのクラス$ P ^ g $、$ NP ^ g
$などを持つ。$ f $は金属学において無作為に選ばれたので、$ P ^ g ne NP ^ g $は確率1で真である。

Question 1: Is $P^g = NP^g$ independent over
$ZFC^f$?

証拠はすぐに分かります。$ ZFC ^ f $の有限の証明は、ほとんどの有限の$ g
$の値で調べることができます。しかし、私は定義が分かりやすいとは確信していません。

Question 2: Is there a good reference exploring
this type of logic + random oracle construction?

ベストアンサー

質問1ではい(ZFCが一貫していると仮定します)。 $ f $がランダムになる必要はありません。証明のために、NP $ ^ h
= $ P $ ^ h $でオラクル$ h $があるという事実も使う必要があります。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です