Collaborative Research: Algebra and Algorithms, Structure and Complexity Theory

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

• 批准号: 1500235
• 负责人: Ralph Freese
• 金额: $ 3.95万
• 依托单位: University of Hawaii
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-15 至 2018-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1500235&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软件的进一步开发，UACalc是一个用于处理涉及代数结构的计算的证明助手。研究人员将努力确定Feder和Vardi的CSP二分猜想的真实性，该猜想指出，每个有限模板的约束满足问题都是在多项式时间内可解的，或者是NP完全的。他们将通过提炼与弱幂等Maltsev条件相容的关系和具有有限相关克隆的代数的知识来进一步发展CSP的代数方法。该项目的第二个目标涉及与它们生成的簇相关的有限代数的性质的可计算识别，例如具有有限剩余界的有限代数是否是有限公理的，或者有限代数是否可以用作自然对偶的特征标值代数。该项目更切实的成就之一将是扩大和加强UACalc软件的适用性。该项目这一部分的议程包括并行化重要的子例程，构建猜想测试和搜索功能，添加进一步的算法，以及进一步发展用户和贡献者社区。