Research in universal algebra and constraint satisfaction

普适代数与约束满足研究

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

Ordinary algebra studies the laws of addition, subtraction, multiplication and division of ordinary numbers. Branches of modern algebra study certain "nonstandard" systems of algebra which arise in various contexts. A simple example is Boolean algebra, which is the system of laws modeled by the operators AND, OR, XOR (“exclusive OR”), and NOT as they operate on the two boolean truth values 0 ("false") and 1 ("true"). Much more complicated systems of algebra, most 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 seeks to solve several long-standing conjectures in universal algebra and theoretical computer science. 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; my research will aim to extend the domain in which the conjecture is known to be true. The second conjecture is a famous problem from theoretical computer science called the “Constraint Satisfaction Problem Dichotomy Conjecture.” This 15-year-old conjecture asserts that, for a certain class of computational problems, each problem in the class is either computationally relatively easy, or is impossibly hard (in a precise sense); in other words, there is no problem in the class with intermediate difficulty. It turns out that the tools of universal algebra are especially useful in tackling this problem. My research aims to significantly enlarge the cases for which the conjecture is confirmed. I will also work to extend the domain for which a related conjecture, regarding those computational problems in the class that can be solved very easily, is confirmed. A final cluster of conjectures on which I will work 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. I hope to shed light on these mysteries by finding reasons to justify the observed patterns. This is pure, curiosity-driven research. It 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、XOR（“异或”）和NOT建模的定律系统，因为它们对两个布尔真值0（“假”）和1（“真”）进行运算。更复杂的代数系统，其中大多数是奇异的，其中一些在物理学，化学，理论计算机科学和工程学中很有用，可以被发明，研究和建模。泛代数是对非标准代数定律及其模型中的模式和限制的一般研究。 这项计划资助的研究旨在解决通用代数和理论计算机科学中的几个长期存在的问题。 第一个猜想描述的情况下，（据信）应该意味着法律的非标准系统的代数都将推导出一些固定的，有限的一套基本法律。 这个猜想在很多情况下都是正确的;我的研究将致力于扩展这个猜想正确的领域。 第二个猜想是理论计算机科学中一个著名的问题，叫做“约束满足问题二分法猜想”。 这个15年前的猜想断言，对于某一类计算问题，该类中的每个问题要么在计算上相对容易，要么是不可能困难的（在精确意义上）;换句话说，该类中没有中等难度的问题。 事实证明，泛代数的工具在解决这个问题时特别有用。 我的研究旨在显著扩大证实猜想的案例。 我还将努力扩展一个相关猜想的领域，关于那些在类中可以很容易地解决的计算问题，得到证实。 我将要研究的最后一组结构涉及非标准代数系统的某些“不可约”模型的分布。 在相当弱的假设下，当一个代数系统没有无限大小的不可约模型时，有限大小系统的不可约模型似乎遵循某些我们目前无法解释的规律性模式。 我希望通过寻找理由来证明观察到的模式，从而阐明这些谜团。 这是纯粹的，好奇心驱动的研究。它将服务于世界范围内的纯数学家和理论计算机科学家，他们寻求理解由代数建模的抽象数学现象。 它将为加拿大服务，培训学生进行尖端研究，并通过解决备受瞩目的问题为加拿大带来声望。