$ BPP $と$ PSPACE $を解決することの意義

複雑さクラス$ BPP $、$ P $、$ NEXP $の間の関係は現在不確定です。時間階層の定理によって$ P neq
EXP $を知っていますが、$ BPP = P $(信じられないほど)または$ BPP = EXP
$(そう思わない)またはその中間にあるかどうかは分かりません。しかし、我々は、これを何らかの方法で決定することに起因するいくつかの興味深い示唆を知っています。

  • $ P neq BPP はP neq NP $を意味する
  • $ P = BPP はBPP neq EXP $を意味します。

等々。

私が疑問に思うのは、$ BPP $から$ PSPACE $の関係がこれらの関係にどのような影響を与えるのでしょうか?

たとえば、$ BPP subset PSPACE $があることはわかっていますが、$ BPP = PSPACE
$(考えられないと思われる)か$ BPP neq PSPACE $のいずれかがわかりません。

この関係が最終的に一方的に決定された場合、$ BPP $と$ EXP $、$ BPP $と$ P $、$ P $と$
PSPACE $の関係について、私たちが知っていることに何らかの影響を与えるでしょうか? 、$ PSPACE $と$ EXP
$、または$ P $と$ NP $のどちらにあるのでしょうか?

逆に、これらの他のクラスの未定の関係について何かを解決することは、$ BPP neq PSPACE
$という証明を意味するか?

私は$ BPP = PSPACE $が少なくとも$ BPP $が含まれている第2レベルまで$ PH
$崩壊させると信じています。それが完全に崩壊するかどうかはわかりません。

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

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