Collaborative Research: Algebra and Algorithms, Structure and Complexity Theory

该项目是五所大学数学研究人员之间的合作，其中包括职业生涯早期的年轻数学家，他们正在联手解决数学逻辑、代数和计算机科学融合的基本问题。总体目标是加深对如何识别某些类型计算问题的复杂性的理解。该项目侧重于一组数学问题，其解决方案将产生关于约束满足问题复杂性的新信息。这些问题包括调度问题、资源分配问题和可简化为求解线性方程组的问题。CSP在理论上是可解的，但有些不能有效地解。本研究旨在厘清易处理个案与难处理个案之间的界限，并为易处理个案的解决提供有效的演算法。数学和计算机科学中的许多基本问题都可以用CSP来表述，这方面的进展将具有实践和理论意义。该项目的第二个组成部分是研究代数中的经典计算问题，以确定它们是否可以通过算法解决。该项目的第三个组成部分是进一步开发UACalc软件，这是一个用于处理涉及代数结构的计算的证明助手。研究人员将努力确定Feder和Vardi的CSP二分猜想的真伪，该猜想表明每个具有有限模板的约束满足问题在多项式时间内可解或NP完全。他们将通过完善与弱幂等Maltsev条件相容的关系和具有有限相关克隆的代数的知识，进一步发展CSP的代数方法。该项目的第二个目标涉及与它们生成的变量相关的有限代数的属性的可计算识别，例如具有有限剩余界的有限代数是否有限公理化，或者有限代数是否可以作为自然对偶的特征值代数。这个项目比较具体的成就之一将是扩大和加强非洲经委会软件的适用性。这部分项目的日程包括并行化重要的子程序、构建猜想测试和搜索特性、添加进一步的算法以及进一步开发用户和贡献者社区。

This project is a collaboration between mathematical researchers at five universities, including young mathematicians at the early stages of their careers, who are joining forces to tackle fundamental problems at the confluence of mathematical logic, algebra, and computer science. The overall goal is to deepen understanding about how to recognize the complexity of certain types of computational problems. The project focuses on a suite of mathematical problems whose solutions will yield new information about the complexity of Constraint Satisfaction Problems. These problems (CSP's) include scheduling problems, resource allocation problems, and problems reducible to solving systems of linear equations. CSP's are theoretically solvable, but some are not solvable efficiently. The research will be aimed at identifying a clear boundary between the tractable and intractable cases, and at providing efficient algorithms for solutions in the tractable cases. Many fundamental problems in mathematics and computer science can be formulated as CSP's, and progress here would have both practical and theoretical significance. A second component of the project investigates classical computational problems in algebra in order to determine whether they are algorithmically solvable. A third component of the project is the further development of the software UACalc, which is a proof assistant developed to handle computations involving algebraic structures.The researchers shall work to decide the truth of the CSP Dichotomy Conjecture of Feder and Vardi, which states that every Constraint Satisfaction Problem with a finite template is solvable in polynomial time or is NP complete. They will further develop the algebraic approach to CSP's by refining knowledge about relations compatible with weak idempotent Maltsev conditions and about algebras with finitely related clones. A second goal of the project concerns the computable recognition of properties of finite algebras connected with the varieties they generate, such as whether a finite algebra with a finite residual bound is finitely axiomatizable, or whether a finite algebra can serve as the algebra of character values for a natural duality. One of the more tangible accomplishments of this project will be a broadening and strengthening of the applicability of the UACalc software. The agenda for this part of the project includes parallelizing the important subroutines, building in conjecture-testing and search features, adding further algorithms, and further developing the community of users and contributors.