Research in universal algebra: constraint satisfaction and residual properties

普适代数研究：约束满足和剩余性质

• 批准号: RGPIN-2019-03931
• 负责人: Willard, Ross
• 金额: $ 1.24万
• 依托单位: University of Waterloo
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=737259
• 关键词: Research; universal; algebra; constraint; satisfaction

Ordinary algebra studies the laws of addition, subtraction, multiplication and division of ordinary numbers. Modern algebra studies "nonstandard" systems of algebra which arise in various contexts. A simple example is Boolean algebra, which is the system of laws modeled by the logical operators AND, OR, and NOT as they operate on the two truth values 0 ("false") and 1 ("true"). Much more complicated systems of algebra, many of them bizarre, some of them useful in physics, chemistry, theoretical computer science and engineering, can be invented, studied, and modeled. Universal algebra is the general study of patterns in, and the limits of, nonstandard laws of algebra and their models. The research to be funded by this proposal has three major parts. First, my team and I will study and reformulate the solutions, announced independently in 2017 by Andrei Bulatov at Simon Fraser University and Dmitriy Zhuk at Lomonosov Moscow State University, of a 20-year-old conjecture in theoretical computer science. This conjecture, called the Constraint Satisfaction Problem Dichotomy Conjecture, asserts that, for a certain class of computational problems, each problem in the class is either computationally easy, or is impossibly hard (in a precise sense); in other words, no problem in the class has intermediate difficulty. The tools of universal algebra were especially useful in proving this conjecture. The goal of this part of my research will be to develop new theories within universal algebra to better explain the discoveries of Bulatov and Zhuk. In the second part, my team and I will work on two 40-year-old unsolved conjectures concerning patterns involving nonstandard laws of algebra and their finite models. The first conjecture describes circumstances which (it is believed) should imply that the laws of a nonstandard system of algebra will all be deducible from some fixed, finite set of basic laws. This conjecture is known to be true in a very large number of cases; our research will aim to extend the domain in which the conjecture is known to be true. The second conjecture concerns the distribution of certain "irreducible" models of a nonstandard system of algebra. Under rather weak assumptions, when an algebraic system has no irreducible models of infinite size, the irreducible models of the system of finite size seem to obey certain patterns of regularity that we currently cannot explain. My team and I hope to shed light on these mysteries by finding reasons to justify the observed patterns. The final part of this project involves exploratory investigations of two additional open problems in universal algebra. This research will serve the world-wide community of pure mathematicians and theoretical computer scientists who seek to understand abstract mathematical phenomena modeled by algebra. It will serve Canada by training students in cutting-edge research, and in bringing prestige to Canada through the solution to high-profile problems.

普通代数研究普通数的加、减、乘、除的规律。现代代数研究在不同背景下出现的“非标准”代数系统。一个简单的例子是布尔代数，它是由逻辑运算符AND、OR和NOT模拟的定律系统，因为它们对两个真值0(“假”)和1(“真”)进行操作。可以发明、研究和模拟更复杂的代数系统，其中许多系统很奇怪，其中一些在物理、化学、理论计算机科学和工程中很有用。泛代数是对非标准代数定律及其模型中的模式及其极限的一般研究。这项提案将资助的研究包括三个主要部分。首先，我和我的团队将研究和重新制定解决方案。西蒙·弗雷泽大学的安德烈·布拉托夫和莫斯科国立大学的德米特里·朱克于2017年独立宣布了关于理论计算机科学中一个20年前的猜想的解决方案。这种被称为约束满足问题二分猜想的猜想断言，对于某一类计算问题，该类中的每个问题要么在计算上容易，要么在精确意义上是不可能的困难；换句话说，类中没有任何问题具有中等难度。万能代数的工具在证明这一猜想时特别有用。我这部分研究的目标将是在普适代数中发展新的理论，以更好地解释布拉托夫和朱克的发现。在第二部分中，我和我的团队将致力于两个40年来尚未解决的猜想，这些猜想涉及到非标准代数定律及其有限模型的模式。第一个猜想描述了这样的情况，即一个非标准代数系统的定律都可以从一些固定的、有限的基本定律中推导出来。已知这一猜想在非常多的情况下是正确的；我们的研究将旨在扩大已知猜想为真的领域。第二个猜想涉及非标准代数系统的某些“不可约”模型的分布。在相当弱的假设下，当一个代数系统没有无限大的不可约模型时，有限大小的系统的不可约模型似乎服从某些我们目前无法解释的规律性模式。我和我的团队希望通过找到理由来证明观察到的模式是正确的，从而阐明这些谜团。这个项目的最后部分包括对泛代数中另外两个公开问题的探索性调查。这项研究将为世界各地的纯数学家和理论计算机科学家社区服务，他们试图理解由代数建模的抽象数学现象。它将通过培训学生进行尖端研究来服务于加拿大，并通过解决引人注目的问题为加拿大带来声望。