無秩序化の観点から、より強い回路下限は何を与えるのでしょうか?

We have $EXPnotsubseteq P/polyimplies BPPsubseteq
io-DTIME(2^{n^epsilon})$ at every $epsilon>0$.

This is essentially $DTIME(2^{O(n)})notsubseteq P/polyimplies
BPPsubseteq io-DTIME(2^{n^epsilon})$ at every
$epsilon>0$.

より強力なデランダマイズの結果はありますか?

$ a(n)$は構成可能な超多項式であればいつでも構いません。

  1. $ NTIME(a(n)) not subseteq P/poly $は何を与えるのですか?

  2. $ DTIME(a(n)) not subseteq P/poly $は何を与えるのですか?

これらは$ BPP subseteq io-DTIME(poly(n))$や何か弱いものを与えますか?

ベストアンサー

It is known that if $E = DTIME(2^{O(n)})$ is not contained in
$SIZE(2^{varepsilon cdot n})$ for some $varepsilon>0$ then
$BPP = P$ (https://dl.acm.org/citation.cfm?id=258590).

(実際には若干強い仮定が必要です。つまり、$ E $と$ SIZE(2 ^ { varepsilon cdot
n})$の間の分離は、ほぼすべての入力の長さにわたって保持されるはずです。Ryan O’Donnelでる。)

More generally, this paper gives a direct optimal translation of
any circuit lower bound into a corresponding derandomization
result: http://users.cms.caltech.edu/~umans/papers/SU01-final.pdf

返信を残す

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