对称指数时间算法需要接近最大的电路规模

《Journal of the ACM》：Symmetric Exponential Time Requires Near-Maximum Circuit Size

对称指数时间（S?E）中存在语言要求电路复杂度至少2?/n，拓展至Σ?E∩Π?E和ZPE^NP的构造，突破此前半指数下界，最小指数电路类提升为Δ3E。

　　

摘要

我们证明了在 S₂E（对称指数时间）中存在这样一种语言：对于任何输入长度，其所需的电路复杂度至少为 2ⁿ/n。特别地，上述结论也适用于 Σ₂E∩Π₂E 这一类语言。我们的证明具有相对性。此前，对于这些复杂度类，人们只知道“半指数级”的电路复杂度下界；而已知需要指数级电路复杂度的最小复杂度类是 ${\mathrm{ZPE}}^N$（Miltersen、Vinodchandran 和 Watanabe，COCOON’99）。我们的电路复杂度下界是基于一个无条件零错误伪确定性算法得出的，该算法利用 NP 神谕来解决范围避免（Range Avoidance）问题。此外，这个算法还暗示了针对 Ramsey 图、刚性矩阵、双源提取器（two-source extractors）、线性码以及 K^poly 随机字符串的 FZPP^NP 构造方法，且这些构造方法的参数几乎是最优的。