自动机理论在非交换多项式身份测试中的应用

"这篇论文探讨了非交换多项式身份测试及其在自动机理论中的应用，同时也涉及到了交换多项式身份测试以及在有限交换环中的复杂性问题。" 文章详细介绍了利用自动机理论来解决非交换多项式身份测试问题的新方法。非交换多项式身份测试是一个重要的算法问题，它涉及判断给定的非交换电路是否计算出零多项式。在本文中，作者Arvind、Partha Mukhopadhyay和Srikanth Srinivasan提出了一个确定性的多项式时间测试算法，该算法能够在时间复杂度为多项式于输入的非交换电路的大小d、变量数量n以及电路的大小|C|的情况下运行。此外，这种方法也适用于黑箱设置，能够以多项式时间复杂度重构具有t个项的d次非交换黑箱多项式。 作者进一步将这种思想应用到非交换代数分支程序（ABPs）的重构中，即便是在黑盒模型中，他们也能在确定性多项式时间内重建ABP。这扩展了Nisan和Raz-Shpilka在之前工作中对ABPs的研究。 文章还讨论了当输入多项式的系数来自任意有限交换环且使用统一编码时，交换多项式身份测试的复杂性问题。在这种情况下，多项式身份测试的某些算法仍然有效。尽管Impagliazzo和Kabanets的工作显示了该问题与证明超多项式电路下界一样困难，但该文指出，即使对于深度为3的算术电路，该问题仍然是未解的，特别是那些具有无限域的双稳态门的电路。 这篇论文通过引入自动机理论的方法，为非交换和交换多项式身份测试提供了解决方案，并深入探讨了这些问题在不同环境下的复杂性，尤其是当系数来自于有限交换环时。这些发现对理解和优化算法复杂性，以及推动相关领域理论研究有着重要意义。