Structure and algorithms, between logic and algebra

结构与算法，逻辑与代数之间

• 批准号: 0604065
• 负责人: Ralph McKenzie
• 金额: --
• 依托单位: Vanderbilt University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2006
• 资助国家: 美国
• 起止时间: 2006-06-15 至 2010-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0604065&HistoricalAwards=false
• 关键词: Structure; algorithms; between; logic; 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.

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