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.