Research Perspectives - Tools for Visualisation of Portfolios
EPSRC logo

EPSRC Database


Source RCUK EPSRC Data

EP/H026835/1 - Descriptive Complexity with Algebraic Operators

Research Perspectives grant details from EPSRC portfolio

http://www.researchperspectives.org/gow.grants/grant_EPH0268351.png

Professor A Dawar EP/H026835/1 - Descriptive Complexity with Algebraic Operators

Principal Investigator - Computer Laboratory, University of Cambridge

Scheme

Standard Research

Research Areas

Theory of Computation Theory of Computation

Start Date

04/2010

End Date

03/2014

Value

£424,833

Similar Grants

Automatic generation of similar EPSRC grants

Similar Topics

Topic similar to the description of this grant

Grant Description

Summary and Description of the grant

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.

Structured Data / Microdata


Grant Event Details:
Name: Descriptive Complexity with Algebraic Operators - EP/H026835/1
Start Date: 2010-04-01T00:00:00+00:00
End Date: 2014-03-31T00:00:00+00:00

Organization: University of Cambridge

Description: 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 polyno ...