论文标题
最大自动复杂性和无上下文的语言
Maximal automatic complexity and context-free languages
论文作者
论文摘要
令$ a_n $表示非确定性自动复杂性，\ [ l_ {k，c} = \ {x \ in [k]^*：a_n（x）> | x |/c \}。 \]特别是，$ l_ {k，2} $是$ a_n $最大的所有$ k $ - ary单词的语言，而$ l_ {k，3} $在复杂和简单之间给出了粗糙的划分线。令$ \ mathbf {cfl} $表示由所有不含上下文的语言组成的复杂性类。虽然不知道$ l_ {2,2} $是无限的，但Kjos-Hanssen（2017）表明$ L_ {3,2} $是$ \ Mathbf {Cfl {Cfl} $ - Immune，但不是$ \ Mathbf {Cocfl {Cocfl} $。我们通过显示$ l_ {3,2} \ in \ mathbf {CoCfl} $来完成图片。 转向布尔电路的复杂性，我们表明$ l_ {2,3} $是$ \ mathbf {sac}^0 $ -Immune和$ \ Mathbf {sac}^0 $ -coimmune。这里$ \ mathbf {sac}^0 $表示复杂性类，由所有语言组成的所有语言组成，该语言由（不均匀）恒定深度电路，具有半无功能的Fanin。 至于算术电路，我们表明$ \ {x：a_n（x）> 1 \} \ not \ in \ oplus \ mathbf {sac}^0 $。特别是，$ \ mathbf {sac}^0 \ not \ subseteq \ oplus \ oplus \ mathbf {sac}^0 $，它解析了复杂性动物园的开放含义。
Let $A_N$ denote nondeterministic automatic complexity and \[ L_{k,c}=\{x\in [k]^* : A_N(x)> |x|/c\}. \] In particular, $L_{k,2}$ is the language of all $k$-ary words for which $A_N$ is maximal, while $L_{k,3}$ gives a rough dividing line between complex and simple. Let $\mathbf{CFL}$ denote the complexity class consisting of all context-free languages. While it is not known that $L_{2,2}$ is infinite, Kjos-Hanssen (2017) showed that $L_{3,2}$ is $\mathbf{CFL}$-immune but not $\mathbf{coCFL}$-immune. We complete the picture by showing that $L_{3,2}\not\in\mathbf{coCFL}$. Turning to Boolean circuit complexity, we show that $L_{2,3}$ is $\mathbf{SAC}^0$-immune and $\mathbf{SAC}^0$-coimmune. Here $\mathbf{SAC}^0$ denotes the complexity class consisting of all languages computed by (non-uniform) constant-depth circuits with semi-unbounded fanin. As for arithmetic circuits, we show that $\{x:A_N(x)>1\}\not\in\oplus\mathbf{SAC}^0$. In particular, $\mathbf{SAC}^0\not\subseteq\oplus \mathbf{SAC}^0$, which resolves an open implication from the Complexity Zoo.
