Group-Theoretic Computation: Complexity and Applications

本研究涉及群体的基本计算问题。一个中心主题涉及图同构测试和相关问题。 多项式时间的结果以及其他复杂性理论问题正在扩展到矩阵群，在数学科学中的应用的共同领域。 实施和实验是伴随着理论，置换组和新的矩阵组的方法正在有效地实施，使保证渐近的时间被保留。 同样的群论问题是相关的一种新的方法来约束满足问题，利用对称性，可以增加现有的应用系统。

The research deals with basic computational problems for groups. A central theme involves graph-isomorphism testing and related issues. Polynomial-time results as well as other complexity theoretic issues are being extended to matrix groups, the common domain for applications in the mathematical sciences. Implementation and experimentation is accompanying the theory, and both the permutation-group and new matrix-group methods are being efficiently implemented so that the guaranteed asymptotic timings are retained. The same group-theoretic problems are relevant to a new approach to constraint-satisfaction problems that exploits symmetries and can augment existing applied systems.