Structure and algorithms, between logic and algebra

McKenzie将研究算法问题，涉及由它们产生的变量和准变量决定的有限代数的性质，以及结构问题，涉及必要的代数性质，这些性质必须在局部有限变量或准变量中成立，因为该类具有通过逻辑或集合论方法定义的一些自然性质。突出的算法问题：是否存在一种算法来确定在有限代数F中有效的拟方程是否是有限基的？是否存在一种算法来确定F生成的拟变量是否具有自然对偶性？具有有限等式基的有限代数是递归可枚举的吗？是否一类有限代数产生一个剩余的大变种递归枚举？在重要的结构问题中：对于有限生成的变量是有限可决定的，或者只有几个模型，什么样的代数性质集合是必要和充分的？他将研究一个代数猜想，如果得到证明，将为理论计算机科学的约束满足问题建立二分猜想的一个重要案例：满足半分配型中的每一个有限代数F都具有有限的关系宽度。首席研究员认为，一方面，识别有限代数基本属性的算法的存在或不存在，另一方面，在代数中表现出的结构复杂性水平之间的相互作用的研究——这个项目的全部内容——不仅有可能扩大我们对有限代数系统中结构可能性的理解（它已经做到了），而是要在理论计算机科学上产生根本性的突破。最有可能很快发生这种情况的地方是约束满足问题（CSP）的代数方法。约束满足问题的具体实例，包括图同态问题，在人工智能、计算机科学、数据库理论、调度、网络、硬件验证等许多领域中无处不在。代数方法将一些最发达的通用代数领域，特别是由首席研究员开发的驯服同余理论的机制，用于研究与CSP相关的组合问题；它可能在其他计算范式的研究中有潜在的应用，比如近似和随机算法，以及量子计算。

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.