Descriptive Complexity with Algebraic Operators

计算复杂性的研究关注于理解是什么使某些计算任务本质上难以解决。在这种情况下，可以通过算法来解决的问题被认为是可行的，或者是有效地可解的。描述复杂性领域的一个长期的研究问题是对那些可行的问题进行完整的分类。这样一个完整的分类将采取一种形式语言(或逻辑)的形式，在这种语言中，人们可以定义所有可行的问题，但不能定义其他问题。众所周知，基于归纳和计数的语言不足以满足这一目的，并且最近发现，添加基于线性代数的某些运算符可以扩展这种语言的能力。我们的研究旨在通过了解这些扩展语言的力量来实现这一突破。为此，我们将开发新的方法来分析表达能力，并使用此方法来确定新定义的语言是否确实捕获了可行计算的能力。我们还将调查这些语言是否在有趣的特殊情况下捕获可行计算。

The study of computational complexity is concerned with understanding what makes certain computational tasks inherently difficult to solve. In this context, problems that can be solved by means of algorithms that take a number of steps bounded by a polynomial are considered to be feasible, or efficiently solvable. A long standing research concern in the field of descriptive complexity has been to give a complete classification of those problems that are feasible. Such a complete classification would take the form of a formal language (or a logic) in which one could define all the feasible problems, but no others. It has been known for some time that languages based on induction and counting are not sufficient for this purpose and it has recently been discovered that adding certain operators based on linear algebra can extend the power of such languages. Our research aims at building on this breakthrough by understanding the power of these extended languages. To do this we will develop new methods to analyse the expressive power and use this to determine whether or not the newly defined languages do capture the power of feasible computation.We will also investigate whether these languages capture feasible computation in interesting special cases.