| EPSRC Reference: |
GR/H81108/01 |
| Title: |
DESCRIPTIVE COMPLEXITY THEORY |
| Principal Investigator: |
Stewart, Professor IA |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
Swansea University |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
12 January 1993 |
Ends: |
11 July 1996 |
Value (£): |
100,934
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
The-general objective of the research is to investigate the roles of logic and (finite) model theory in theoretical computer science, with emphasis on the expressibility of certain logics in relation to the classification of problems according to their computational complexity. More specific aims are to investigate(i) the capture of complexity classes using logics involving both ordered and unordered structures;(ii) the completeness of problems for complexity classes with respect to extremely weak logical reductions; and(iii) the refined (logical) categorisation of complete problems which were previously considered to be equivalent.Progress:Substantial progress has been made since the start of the grant towards attaining the technical objectives mentioned above. Dr. Stewart proved the surprising result that the complexity class captured by full Hamiltonian path logic (on ordered structures) is the class of problems solvable by a logspace oracle machine with an NP oracle: the paper has appeared in the journal Fundamenta Informaticae after being presented at Computer Science Logic CSL'93 , Italy. This work has motivated substantial research by Professors Janos Makowsky (Technion, Israel) and Georg Gottlob (TU Wien, Austria) on extending this result. Also, Dr. Stewart has shown how generalised quantifiers can be amalgamated with the least fixed point operator to provide a logical characterisation of the class of problems accepted by a polynomial time oracle machine with access to an NP oracle: these results were presented at Computer Science Logic CSL'94 , Swansea. The research in these two papers goes towards the securing of aim (i). As regards aim (ii), Dr. Stewart has developed new techniques to prove completeness for complexity classes via extremely restricted logical reductions and has applied these techniques to show that many traditional complete problems associated with finding paths in graphs remain complete via these reductions: the paper is to appear in the journal Information and Computation . As regards aim (iii), Dr. Stewart has considered the role of monotonicity in the expressive power of logics formed using generalised quantifiers corresponding to NP-complete problems: these results have been published in the journal Mathematical Logic Quarterly . In all, Dr. Stewart has 6 journal papers appear or to appear which have benefited from support of the research grant and also 2 papers appear in conference proceedings. The appointment of Dr. Dawar as a Senior Research Assistant has been a great success. The grant has enabled Dr. Dawar to develop and pursue numerous research collaborations in finite model theory and descriptive complexity theory with researchers in other institutions and also with Dr. Stewart at Swansea. Dr. Dawar has enjoyed short research visits to INRIA, Rocquencourt, France; the University of Helsinki, Finland; the University of Aachen, Germany; and the University of Pennsylvania, U.S.A., all at the invitation of the host institution. Publications have followed from these collaborations although most are still ongoing: for example, papers have been presented at IEEE Symposium for Logic in Computer Science, 1994 and the Logic Colloquium: the Annual European Summer Meeting of the ASL , and papers are to appear in the journals Logic and Computation and Information and Computation . All work is in pursuit of the above general aim. In summation, the progress made byDr. Stewart and Dr. Dawar has been most substantial and both have benefited greatly from the support of the grant. The general goals of the research however are long term and these is much work still to do.
|
|
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: |
|
| Further Information: |
|
| Organisation Website: |
http://www.swan.ac.uk |