Details of Grant 

EPSRC Reference:	EP/D03809X/1
Title:	Abstract Measures of Low-Level Computational Complexity
Principal Investigator:	Beckmann, Professor A
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department:	Computer Science
Organisation:	Swansea University
Scheme:	First Grant Scheme Pre-FEC
Starts:	01 September 2006	Ends:	31 August 2009	Value (£):	124,993
EPSRC Research Topic Classifications:	Fundamentals of Computing
EPSRC Industrial Sector Classifications:	No relevance to Underpinning Sectors
Related Grants:
Panel History:
Summary on Grant Application Form
Assume you are a student living in a big town. You have a lot of friends who you want to invite to your birthday party. The party will take place at a location which is so cool that it is hard to find, and as you are running low of money you have to ride your bike to your friend's homes to distribute invitation letters including a map of the party place.You don't have much time, so you try to find the shortest route through the town which connects all your friends homes, and as you have a lot of computer skills you quickly write a small program which does this for you. But unfortunately, the program does not come to an end after several hours of work, so you have to distribute the letters without knowing the shortest tour. What happened?The problem of finding such a shortest tour is well known in theoretical computer science under the name Travelling Salesperson Problem (TSP). It is one of the hardest problems in a class of problems denoted by NP for which practical programs are not known to exist. The class of problems which have in this sense practical programs is denoted by P. So, the question if there exists a practical program for TSP, i.e. a program which can find a tour to your friend's homes in say half an hour, is the same as asking whether P is the same as NP. This P versus NP question is one of the most important questions in contemporary mathematics and theoretical computer science - the Clay Mathematics Institute offers $1 million for its solution! In the present project we try to better understand the nature of such classes of computational problems and logical systems describing them by searching for ideal objects which give good characterisations of such classes. What's that? Well, for classes of strong computational problems these proposed ideal objects are well known: they are given by infinitary objects (formed by beautiful extensions of the natural numbers to the infinite) called proof theoretic ordinals , and, astonishingly, they describe precisely the computational content of such computational classes and logical systems related to computational classes (and much more). With this project we will try to find similar correspondences for weak , i.e., low-level, computational classes like P and NP, using so called dynamic ordinals . In particular, we investigate whether dynamic ordinals can be used to describe the computational content of logical systems (called bounded arithmetic ) related to P and NP. The aim is to obtain a deeper understanding of such computational classes like P and NP, and logical systems related to them like bounded arithmetic, and in particular of the relationship between computational classes and logical systems. This might help us to find new approaches to separation questions of logical system, which are the analogy to the P versus NP question and considered to be equivalently hard to answer.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk Summary Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:	http://www.cs.swan.ac.uk/~csarnold/amllcc/
Further Information:
Organisation Website:	http://www.swan.ac.uk