Structure and algorithms, between logic and algebra

点击翻译按钮获取中文摘要

McKenzie will investigate algorithmicquestions which involve properties of finite algebras determined by thevarieties and quasi-varieties they generate, andstructural questions which involve the necessary algebraic propertiesthat must be true throughout a locally finite variety or quasi-variety as a consequence of that class possessing some natural property defined through logical or set-theoretic means. The outstanding algorithmic questions: Is there an algorithm todetermine if the quasi-equations valid in a finite algebra F are finitely based? Is there an algorithm to determine if the quasi-variety generated by F possesses a natural duality? Is the class of finite algebras possessing a finite equational basis recursively enumerable? Is the class of finite algebras generating a residually large variety recursively enumerable? Among the important structural questions: What collection of algebraicproperties is necessary and sufficient for a finitely generated variety tobe finitely decidable, or to have few models? He will work on an algebraic conjecture that, if proved, would establish animportant case of thedichotomy conjecture for the constraint satisfaction problem oftheoretical computer science: every finite algebra F in a meet semi-distributivevariety has finite relational width.The principal investigator believes that researchinto the interplay between, on the one hand, the existence or nonexistenceof algorithms to recognize fundamental properties of finite algebras, and on the other hand, the levels of structural complexity manifested in the algebras---what this project is all about---has the potential not only to expand our understanding of the structural possibilities in finite algebraic systems (which it has already done), but to producefundamental breakthroughs in theoretical computer science.The most likely place for this to occur soon is in the algebraic approachto the constraint satisfaction problem (CSP).Specific instances of the constraint satisfaction problem, including graph homomorphism problems,are ubiquitous in many areas of artificial intelligence, computerscience, database theory, scheduling, networking, hardware verification, etc. The algebraic approach puts some of the most developed areas ofuniversal algebra, especially the machinery of tame congruence theorydeveloped by the principal investigator, to work in the study of combinatorial problems related to the CSP;and it may have potential applicationsin the study of other computational paradigms, such as approximation and randomized algorithms, and quantum computation.