论文标题
下界和硬度放大度的均值缩小细胞自动机
Lower Bounds and Hardness Magnification for Sublinear-Time Shrinking Cellular Automata
论文作者
论文摘要
最小电路尺寸问题（MCSP）是一个字符串压缩问题，其中参数$ s $，鉴于布尔函数的真实表超过了长度$ n $的输入，必须回答是否可以通过$ s（n）\ ge n $的大小的布尔电路来计算它。最近，McKay，Murray和Williams（Stoc，2019年）证明了MCSP涉及（一通）流媒体算法的硬度放大结果：对于任何合理的$ s $，如果没有$ \ Mathsf {poly}（p poly}（s（s（n）），$ - $ \ mathsf for $ \ mathsf {n） $ \ mathsf {mcsp} [s] $，然后$ \ mathsf {p} \ neq \ mathsf {np} $。我们证明了（严格）缩小细胞自动机（SCAS）的（证明是严格的）模型的结果，该模型是细胞自动机，其细胞可以自发删除自身。我们表明，SCA接受的每种语言也可以通过类似复杂性的流算法来接受，并且我们确定了两个不同方面的SCA比流算法更受限制。我们还表明，即使它承认$ O（\ log n）$ - 空间流算法$ o（\ log n）$更新时间。
The minimum circuit size problem (MCSP) is a string compression problem with a parameter $s$ in which, given the truth table of a Boolean function over inputs of length $n$, one must answer whether it can be computed by a Boolean circuit of size at most $s(n) \ge n$. Recently, McKay, Murray, and Williams (STOC, 2019) proved a hardness magnification result for MCSP involving (one-pass) streaming algorithms: For any reasonable $s$, if there is no $\mathsf{poly}(s(n))$-space streaming algorithm with $\mathsf{poly}(s(n))$ update time for $\mathsf{MCSP}[s]$, then $\mathsf{P} \neq \mathsf{NP}$. We prove an analogous result for the (provably) strictly less capable model of shrinking cellular automata (SCAs), which are cellular automata whose cells can spontaneously delete themselves. We show every language accepted by an SCA can also be accepted by a streaming algorithm of similar complexity, and we identify two different aspects in which SCAs are more restricted than streaming algorithms. We also show there is a language which cannot be accepted by any SCA in $o(n / \log n)$ time, even though it admits an $O(\log n)$-space streaming algorithm with $O(\log n)$ update time.
