Unconditional Lower Bounds against Advice
Unconditional Lower Bounds against Advice
复制标题
反对建议的无条件下限
DOI：
10.1007/978-3-642-02927-1_18
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
R. Santhanam
中科院分区：
文献类型：
--
作者：
H. Buhrman;L. Fortnow;R. Santhanam
我们显示了针对多项式时间类别的指数时间类别的几个无条件的下限，其中包括：1对于任何常数c，$ {\ sf nexp} \ not \ subseteq {\ rm {\ rm {\ rm {\ sf p}}}^{\ sf np np np [\ sf np np [ n^c]}/n^c $ 1对于任何常数c，$ {\ sf maexp} \ not \ subseteq {\ rm {\ sf ma}}}/n^c $ 1 $ {\ sf bpexp} \ not \ subseteq {\ sf bpp}/n^{o（1）} $
以前，即使NEXP *** np/n 0.01也未知。对于概率类别，以前不知道针对建议的统一指数时间的下限。
我们还考虑了是否可以将这些下限用于几乎所有输入长度而不是无限的问题。我们给出了一个oracle，相对于哪个nexp *** io np，它提供了证据表明当前技术是不可能的。
We show several unconditional lower bounds for exponential time classes against polynomial time classes with advice, including: 1 For any constant c , ${\sf NEXP} \not \subseteq {\rm{\sf P}}^{\sf NP[n^c]}/n^c$ 1 For any constant c , ${\sf MAEXP} \not \subseteq {\rm {\sf MA}}/n^c$ 1 ${\sf BPEXP} \not \subseteq {\sf BPP}/n^{o(1)}$
It was previously unknown even whether NEXP *** NP/n 0.01. For the probabilistic classes, no lower bounds for uniform exponential time against advice were known before.
We also consider the question of whether these lower bounds can be made to work on almost all input lengths rather than on infinitely many. We give an oracle relative to which NEXP *** io NP, which provides evidence that this is not possible with current techniques.