论文标题
司额概率的蜂窝自动机
Sublinear-Time Probabilistic Cellular Automata
论文作者
论文摘要
我们提出并研究了均值一维细胞自动机的概率模型。特别是，我们修改了ACA模型（这是蜂窝自动机的模型，并且仅当所有单元同时接受时接受，因此每个单元都会改变其状态，不仅取决于其在其附近看到的状态，而且还取决于其自身的无偏硬币。所得模型被称为概率ACA（PACA）。我们考虑模型的一条和双面错误版本（与$ \ Mathsf {rp} $和$ \ Mathsf {Bpp} $相同的精神，并在他们可以一直识别到$ o（\ sqrt {n}）之间的语言类别之间建立一个分离。结果，我们有一个$ω（\ sqrt {n}）$下限，用于降低恒定时间两边误差PACA（使用确定性ACA）。我们还证明，对于各种$ t（n）=ω（\ log n）$的$ t（n）$ time pacas（to多项式确定性蜂窝自动机）的范式化意味着$ \ mathsf {rp} $（e.g.，$ \ mathsf}的非平凡贬值结果。主要贡献是恒定时间PACA类的几乎完全表征：对于单方面误差，该类等于确定性模型的类别。也就是说，恒定时间单侧误差PACA只能在时间复杂性的恒定乘法开销中完全取代。至于双面错误，我们确定了一个天然类，我们称之为可线测试的语言（$ \ m m i \ m rlt {llt} $），并证明，通过$ \ \ mthsf {llt} $ of Uniove and Systecelect and the Clangue Clangagage，在不变的两面误差下可以决定的语言“夹在”之间。 （$ \ mathsf {ltt} $）。
We propose and investigate a probabilistic model of sublinear-time one-dimensional cellular automata. In particular, we modify the model of ACA (which are cellular automata that accept if and only if all cells simultaneously accept) so that every cell changes its state not only dependent on the states it sees in its neighborhood but also on an unbiased coin toss of its own. The resulting model is dubbed probabilistic ACA (PACA). We consider one- and two-sided error versions of the model (in the same spirit as the classes $\mathsf{RP}$ and $\mathsf{BPP}$) and establish a separation between the classes of languages they can recognize all the way up to $o(\sqrt{n})$ time. As a consequence, we have a $Ω(\sqrt{n})$ lower bound for derandomizing constant-time two-sided error PACAs (using deterministic ACAs). We also prove that derandomization of $T(n)$-time PACAs (to polynomial-time deterministic cellular automata) for various regimes of $T(n) = ω(\log n)$ implies non-trivial derandomization results for the class $\mathsf{RP}$ (e.g., $\mathsf{P} = \mathsf{RP}$). The main contribution is an almost full characterization of the constant-time PACA classes: For one-sided error, the class equals that of the deterministic model; that is, constant-time one-sided error PACAs can be fully derandomized with only a constant multiplicative overhead in time complexity. As for two-sided error, we identify a natural class we call the linearly testable languages ($\mathsf{LLT}$) and prove that the languages decidable by constant-time two-sided error PACAs are "sandwiched" in-between the closure of $\mathsf{LLT}$ under union and intersection and the class of locally threshold testable languages ($\mathsf{LTT}$).
