Collaborative Research: Algebra and Algorithms, Structure and Complexity Theory

合作研究：代数与算法、结构与复杂性理论

• 批准号: 1500254
• 负责人: Keith Kearnes
• 金额: $ 14.42万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-15 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1500254&HistoricalAwards=false
• 关键词: Collaborative; Research; Algebra; Algorithms; Structure

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.

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