论文标题
稀疏集和最小电路尺寸问题的硬度
Hardness of Sparse Sets and Minimal Circuit Size Problem
论文作者
论文摘要
我们在有限字段上开发了多项式方法，以扩大随机流模型上非确定时间复杂性类中备用集的硬度。我们的结果之一表明，如果存在$ 2^{n^{o（1）}} $ - 在$ ntime（2^{n^{o（1）}）$中设置的稀疏设置，该$没有任何随机流algorithm带有$ n^{o（1）} $更新时间的随机流algorithm $ f（n）$ - 稀疏集是一种最多具有$ f（n）$ n $ $ n $的语言。我们还表明，如果MCSP为$ ZPP $ - 在多项式时间真相表减少下，则$ exp \ not = zpp $。
We develop a polynomial method on finite fields to amplify the hardness of spare sets in nondeterministic time complexity classes on a randomized streaming model. One of our results shows that if there exists a $2^{n^{o(1)}}$-sparse set in $NTIME(2^{n^{o(1)}})$ that does not have any randomized streaming algorithm with $n^{o(1)}$ updating time, and $n^{o(1)}$ space, then $NEXP\not=BPP$, where a $f(n)$-sparse set is a language that has at most $f(n)$ strings of length $n$. We also show that if MCSP is $ZPP$-hard under polynomial time truth-table reductions, then $EXP\not=ZPP$.
