有限自动机群词问题的计算复杂性：一致词问题的 coNP 完全性与压缩词问题的 PSpace 完全性

《Information and Computation》：The word problem for finitary automaton groups

　　

有限自动机群（finitary automaton group）是由一个可逆、确定型有限状态字母到字母转换器（transducer）生成的群，该转换器的唯一环是恒等状态上的自环。研究人员证明，对于有限群的这种表示，一致词问题（uniform word problem）是 coNP（补非确定多项式时间类）完全的（coNP-complete）。此处，输入由一个有限自动机和一个有限状态序列组成，问题是该序列是否在所有输入词上平凡作用。此外，研究人员还证明，相应的压缩词问题（compressed word problem）——其中状态序列以直线程序（straight-line program, SLP）给出——是 PSpace（多项式空间类）完全的（PSpace-complete）。在两种情形下，研究人员给出了从（量化）布尔公式可满足性问题出发的直接归约，并进一步证明，如果将自动机的输入字母表限制为二元字母表，这些问题对其相应复杂度类仍保持完全性。

研究背景与问题。群与自动机之间存在多方面联系。自动机群由可逆、确定型有限状态字母到字母转换器生成，每个状态诱导输入词到输出词的双射，状态序列及其逆在复合下闭包形成群。自动机群包含Grigorchuk群等具有重要群论性质的例子，因而其算法性质受到关注。已有结果表明，自动机表示下若干判定问题仍不可判定，例如存在共轭问题不可判定的自动机群以及阶问题不可判定的自动机群；有限性问题在自动机群上仍开放，而半群情形不可判定。词问题在自动机群中具有特殊地位：它可判定，并且即使生成自动机也作为输入的一致情形，也可在非确定线性空间中求解；已有研究构造出词问题为 PSpace 完全的自动机群。该研究关注Sidki活动层级（Sidki’s activity hierarchy）最低层，即有限自动机与有限自动机群；该层唯一环为恒等状态上的自环，并且该层与所有有限群类一致。因此，研究有限自动机群的词问题等同于研究任意有限群在自动机表示下的词问题。对于有限群，已有Cayley表、矩阵、置换等表示下的一致词问题复杂度结果；该研究选择自动机表示，旨在刻画一致词问题及其压缩版本的精确复杂度，并处理二元字母表限制。Maximilian Kotowsky与Jan Philipp W?chter开展该研究，得到有限自动机群一致词问题为 coNP 完全、压缩词问题为 PSpace 完全的结论，并证明二元输入字母表下仍分别保持完全性。其意义在于给出有限群自动机表示下词问题的精确复杂度界限，并通过直接归约展示逻辑公式在自动机中的模拟方法，为活动层级进一步研究提供思路。

关键技术方法（不超过250字）：研究人员采用平衡迭代换位子（balanced iterated commutator）模拟逻辑合取；将3-CNF可满足性问题归约到R-有限型（R-finitary）自动机族的一致词问题，并以A₅（交错群5次）或Grigorchuk群作为子自动机R；引入有限逼近（finite approximation）与可压缩有限逼近，将非有限型自动机问题化为有限自动机群问题；用直线程序（straight-line program, SLP）编码状态序列，并以猜测-检验算法证明上界；对压缩版本使用3-QBF（量化布尔公式）归约。研究不涉及样本队列，输入为自动机、状态序列或SLP。

研究结果。3. 词问题（The word problem）：研究人员先通过猜测非平凡作用的见证词并逐状态计算其作用，证明一致词问题属于 coNP（Proposition 3.1）。R-有限型自动机（R-Finitary Automata）：定义R-有限型自动机，并证明当R为收缩自动机时，非恒等状态序列存在长度至多为|Q|+Alog|q|+B的见证词（Fact 3.5）。主归约（The Main Reduction）：定理3.6从3-CNF可满足性问题归约到R-有限型自动机族的一致词问题；构造检查赋值与子句的自动机部件，并以平衡迭代换位子构造状态序列q，使得公式可满足当且仅当q非平凡作用，从而得 coNP-hard。有限自动机群的一致词问题（The Uniform Word Problem for Finitary Automaton Groups）：以生成A₅的有限自动机作为R，得到五元字母表下 coNP-hard，与 coNP 上界结合得 coNP-complete（Corollary 3.8）。有限逼近自动机（Finitely Approximable Automata）：定义深度D的有限逼近，说明其可在D以一元给出时于 LOGSPACE 计算（Fact 3.11），并证明收缩R下的R-有限型自动机族有限可逼近（Proposition 3.13）。二元字母表（Binary Alphabet）：利用Grigorchuk群、Example 2.11中的换位子构造以及有限逼近，证明二元字母表下一致词问题仍为 coNP-complete（Theorem 3.14）。4. 压缩词问题（The compressed word problem）：直线程序（Straight-Line Programs）：定义SLP为生成唯一词的上下文无关文法，其生成词长度可相对SLP规模指数增长。压缩词问题（The Compressed Word Problem）：通过猜测见证词并按SLP递归计算状态序列作用而不解压，证明一致压缩词问题属于 PSpace（Proposition 4.2）。从量化布尔公式的归约（A Reduction from Quantified Boolean Formulae）：先说明3-QBF为 PSpace-complete（Theorem 4.3），再以A₅为基础扩展自动机以处理量词与否定，构造SLP生成状态序列q_N，证明公式成立当且仅当q_N非平凡作用，得五元字母表下 PSpace-hard（Proposition 4.4）。有限自动机群的一致压缩词问题（The Uniform Compressed Word Problem for Finitary Automaton Groups）：综合上界与下界得 PSpace-complete（Theorem 4.5）。二元字母表（Binary Alphabet）：定义可压缩有限逼近（compressibly finitely approximable），证明收缩R下的R-有限型自动机族具有该性质（Proposition 4.7），并由Grigorchuk群压缩词问题的 PSpace 完全性归约，得二元字母表下一致压缩词问题仍为 PSpace-complete（Theorem 4.8）。

讨论部分总结与研究结论翻译。讨论部分指出，该研究通过自动机模拟逻辑公式，核心是以特定换位子模拟逻辑合取；这一思路与Barrington关于非可解有限群词问题 NC¹（一类电路复杂度类）完全性的方法相关，并期望可推广到活动层级的进一步下界研究。研究结论（译）：有限自动机群的一致词问题是 coNP 完全的（在 many-one LOGSPACE 归约下），并且当输入自动机字母表固定为五元集时仍成立；若将自动机输入字母表限制为二元字母表，该问题仍为 coNP 完全。相应的一致压缩词问题，其中状态序列由直线程序给出，是 PSpace 完全的（在 many-one LOGSPACE 归约下），并且当输入自动机字母表固定为五元集时仍成立；若将输入字母表限制为二元字母表，该问题仍为 PSpace 完全。研究人员在两种情形下均给出了从（量化）布尔公式可满足性问题出发的直接归约。