Complexity in Algebra and Algebra in Complexity: the role of finite semigroups and general algebra

代数中的复杂性和复杂中的代数：有限半群和一般代数的作用

• 批准号: DP1094578
• 负责人: Prof Marcel Jackson
• 金额: $ 18.06万
• 依托单位: La Trobe University
• 依托单位国家: 澳大利亚
• 项目类别: Discovery Projects
• 财政年份: 2010
• 资助国家: 澳大利亚
• 起止时间: 2010-01-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://dataportal.arc.gov.au/RGS/Web/Grants/DP1094578
• 关键词: Complexity; Algebra; role; finite; semigroups

Algebra and logic form the mathematical framework for expressing and analysing algorithms and their difficulty. We can then scientifically analyse what makes some tasks more difficult than others. This project unifies parallel areas of algebra to focus on two key topics at this interface between algebra and computational complexity. As a flow on, our work can uncover new algorithms for solving constraint problems and for the study of formal languages. With a team of top international researchers developing new interactions between mathematics and the study of algorithms, the project will foster a culture of innovation and bring Australia into the play in this internationally competitive area.

代数和逻辑构成了表达和分析算法及其难度的数学框架。 然后，我们可以科学地分析是什么使一些任务比其他任务更困难。 该项目统一了代数的并行领域，重点关注代数和计算复杂性之间接口的两个关键主题。 作为一个流程，我们的工作可以发现新的算法解决约束问题和形式语言的研究。 该项目由国际顶尖研究人员组成，旨在开发数学与算法研究之间的新互动，将培养创新文化，并将澳大利亚带入这一国际竞争领域。