Structure and algorithms, between logic and algebra

McKenzie将研究算法问题，这些问题涉及由它们生成的簇和准簇确定的有限代数的性质，以及结构问题，这些问题涉及必要的代数性质，这些性质在局部有限簇或准簇中必须为真，因为该类具有通过逻辑或集合论方法定义的某些自然性质。悬而未决的算法问题：有没有一种算法来确定有限代数F中有效的拟方程是否以有限基为基？有没有一个算法来确定由F生成的拟簇是否具有自然对偶性？具有有限等式基的有限代数类是递归可列的吗？生成剩余大簇的有限代数类是递归可数的吗？在重要的结构问题中：什么代数性质的集合是有限生成的簇是有限可判定的，或者有几个模型是充要的？他将致力于一个代数猜想，如果被证明，将为理论计算机科学的约束满足问题建立一个重要的二分法猜想：相交半分配形式中的每个有限代数F具有有限的关系宽度。主要研究人员认为，对一方面存在或不存在识别有限代数的基本性质的算法的相互作用的研究，以及另一方面，代数中所表现的结构复杂性的水平--这个项目的全部内容--不仅有可能扩大我们对有限代数系统中结构可能性的理解(它已经完成了)，而是在理论计算机科学方面产生根本性的突破。这种突破最有可能很快发生在约束满足问题的代数方法中。约束满足问题的具体实例，包括图同态问题，在人工智能、计算机科学、数据库理论、调度、网络、硬件验证等许多领域中普遍存在。代数方法将通用代数的一些最发达的领域，特别是主要研究者开发的驯服同余理论的机械，用于研究与约束满足问题有关的组合问题；它可能会在其他计算范例的研究中有潜在的应用，如近似和随机算法，以及量子计算。

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.