Grant: Discovery Grants Program - Individual
University of Waterloo
$22,000.00
Research in universal algebra
EF 2008-09
Résumé
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 boolean operators AND, OR, XOR, and NOT as they act 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 for which I am seeking funding aims to make progress towards resolving deep theoretical conjectures framed in the language of universal algebra. The first is the "Constraint Satisfaction Problem Dichotomy Conjecture" in theoretical computer science. A large class of computational problems, including problems arising from machine reasoning, scheduling and database theory, can be formulated in a precise framework known as a "constraint satisfaction problem" or CSP. The CSP Dichotomy Conjecture postulates that each CSP is either computationally tractable or impossibly hard; refinements of the conjecture guess the location of the line dividing the former kind from the latter. My proposed research will help prove that large classes of CSPs are tractable.
The second and third conjectures that I will study arise within the "pure" theory of universal algebra. Helping resolve these conjectures will extend mathematicians' knowledge of general nonstandard algebraic systems, which in turn may prove to be useful in unpredicted future applications.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
121349-2008
Name nom
Willard, Ross
Department département
Pure Mathematics
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2008
Competition year année de concours
2008
Award amount
22000
Program id
RGPIN
Program nane en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
336
Committee name en
Pure & Applied Maths - A
Committee name fr
Maths pures et appliquées - A
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
Research subject code
2908
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Algebra
Research subject fr
algèbre
Partie
1
Nb partie
5
Application title
Research in universal algebra
Keyword
NA
Application summary
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 boolean operators AND, OR, XOR, and NOT as they act 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 for which I am seeking funding aims to make progress towards resolving deep theoretical conjectures framed in the language of universal algebra. The first is the "Constraint Satisfaction Problem Dichotomy Conjecture" in theoretical computer science. A large class of computational problems, including problems arising from machine reasoning, scheduling and database theory, can be formulated in a precise framework known as a "constraint satisfaction problem" or CSP. The CSP Dichotomy Conjecture postulates that each CSP is either computationally tractable or impossibly hard; refinements of the conjecture guess the location of the line dividing the former kind from the latter. My proposed research will help prove that large classes of CSPs are tractable.
The second and third conjectures that I will study arise within the "pure" theory of universal algebra. Helping resolve these conjectures will extend mathematicians' knowledge of general nonstandard algebraic systems, which in turn may prove to be useful in unpredicted future applications.