Deciding Identities in Nonassociative Algebras with Dynamic Programming

本研究涉及的算法和计算技术，以确定一个给定的非结合多项式是否是各种非结合代数的恒等式。一般来说，这个问题在计算上是非常困难的，并且现有的方法受到时间和内存需求的限制。本研究中使用的方法是使用动态规划算法。该算法通过构造自由代数的某一同态象来解决该问题。构造代数所需的算术运算的数量受结果代数维数的多项式的限制（但对于许多变体，算法在输入大小上可能不是多项式时间）。使用这种方法，似乎许多以前在计算上不切实际的问题，现在可以用现有的计算机来解决。初步测试表明，这种方法可以在几分钟内确定某些多项式，直到10次，是否在各种交换的四次方结合代数中是恒等式。虽然该方法看起来很有前途，但为了使该方法更实用，还需要研究几个理论问题。目标是在几个特定问题上实现算法的完整版本。其中一个问题就是寻找约旦的身份。另一个问题是确定是否存在非特殊马尔切夫代数。

This investigation is concerned with algorithms and computational techniques to decide if a given nonassociative polynomial is an identity for a variety of nonassociative algebras. In general, this problem is computationally very difficult, and existing methods suffer from prohibitive time and memory requirements. The approach used in this investigation is to use a dynamic programming algorithm. The algorithm solves the problem by constructing a certain homomorphic image of the free algebra. The number of arithmetic operations required to construct the algebra is bound by a polynomial in the dimension of the resulting algebra (but for many varieties the algorithm might not be polynomial-time in the input size). Using this method, it appears that many questions, which previously appeared to be computationally impractical, may now be solved with existing computers. Preliminary tests show that this method can be used to decide in minutes if certain polynomials, up to degree 10, were identities in the variety of commutative, fourth-power-associative algebras. While the method looks promising, several theoretic issues need to be examined in order to make the method more practical. A goal is to implement the full version of the algorithm on several specific problems. One such problem is the search for Jordan s-identities. Another is determining whether there exist nonspecial Malcev algebras.