The Shrinkage Exponent of de Morgan Formulas is 2
The Shrinkage Exponent of de Morgan Formulas is 2
复制标题
德摩根公式的收缩指数为 2
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
Johan Hå stad
中科院分区：
文献类型：
--
作者：
Johan Hå stad
证明了如果满足随机约束的德摩根L公式，则期望剩余规模至多为O(p^2(\log\frac{1}{p})^{3/2}L+p\sqrt L)$.作为推论，我们得到了P中显式函数的$omega(n^{3-o(1)})$公式大小的下界，这是已知的NP中任何显式函数的最强下界。
We prove that if we hit a de Morgan formula of size L with a random restriction from Rp, then the expected remaining size is at most $O(p^2(\log \frac {1}{p})^{3/2}L+p\sqrt L)$. As a corollary we obtain an $\Omega(n^{3-o(1)})$-formula-size lower bound for an explicit function in P. This is the strongest known lower bound for any explicit function in NP.