Research in universal algebra and 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.