Complexity and decidability of algebraic and relational structures

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

This is a proposal to fund my ongoing research in universal algebra, which is a branch of pure mathematics. Broadly speaking, the main long-term goals of my proposed research are (1) to discover unifying patterns in various branches of mathematical knowledge, such as logic,algebra, and discrete mathematics; (2) to study these patterns at an appropriate level of generality; (3) to provide insight into global structure by studying phenomena that occur locally; and (4) to return something of the value to the general mathematical community, by either broadening the knowledge in the respective areas, or by finding multi-disciplinary applications. My research falls mostly within the boundaries of equational logic and its algorithmic aspects. The main object of study of equational logic are nonstandard versions of algebra (equational theories) and their abstract models. The general problem is to determine to what extent the models of these nonstandard versions of algebra can be described. In more detail, I am particularly interested in using the tools of combinatorial-geometric nature to study the local structure of algebras and relational structures; to determine to what extent the global structure will be influenced by this local behaviour; and whether such properties can be recognized algorithmically; and, if so, whether such an algorithm is computationally tractable. The research proposal is motivated, among other questions, by a long-standing open problem in the field of universal algebra, which is to characterize all finitely decidable locally finite varieties.   I aim to make a major contribution in my field of research by solving this problem using the methods of tame congruence theory and model theory.