| EPSRC Reference: |
GR/L77089/01 |
| Title: |
A GENERAL PHASE-STRUCTURED STUDY OF COMPUTATIONALLY HARD PROBLEMS AND EFFICIENT ALGORITHMICS |
| Principal Investigator: |
Dunne, Dr PE |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Liverpool |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 1997 |
Ends: |
30 September 2000 |
Value (£): |
134,777
|
| 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 |
|
The primary concern of the work is to produce a sound general basis for the analytic study and exploitation of phase transition effects in hard combinatorial decision problems. The two principal benefits that will result from such a basis are: an understanding of how such a phenomena may be exploited in the design of classes of fast algorithms for such problems; and secondly, a general model within which novel phase transition results can be derived. In order to address two potential objections to existing experimental studies - that these do not reflect the properties of 'real-world' data and are unsuited to problems lacking an 'obvious' parameter that characterises a phase transition - our work will also examine different empirical frameworks for predicting phase transitions and develop models of probability distributions that go some way to capturing properties of 'real' data for selected important combinatorial problems.
|
|
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.liv.ac.uk |