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.

Research on a characterization of P, i.e. a complete classification of those problems that admit efficient solutions in terms of polynomial-time computability, would have an impact in a number of areas: (1) on designers of database management systems and of query and programming languages to whom it would provide a guideline for the design of systems within which feasible algorithms can be implemented; (2) on software developers in general to whom it would provide a conceptual tool for understanding what problems are feasible; and (3) other users of mathematical results, by enriching the landscape of such results and shaping the way we think about fundamental problems. The primiary means of achieving this impact are twofold. First, the publication of the results in accessible and permanent form. Secondly, in the longer run as results mature, they are taught to students and thereby diffuse through the user community.