EPSRC logo

Details of Grant 

EPSRC Reference: GR/L24014/01
Title: CONSTRAINEDNESS OF COMPUTATIONAL PROBLEMS
Principal Investigator: Prosser, Dr P
Other Investigators:
Gent, Professor IP
Researcher Co-Investigators:
Project Partners:
Department: Computer and Information Sciences
Organisation: University of Strathclyde
Scheme: Standard Research (Pre-FEC)
Starts: 01 October 1996 Ends: 30 September 1999 Value (£): 170,499
EPSRC Research Topic Classifications:
Artificial Intelligence
EPSRC Industrial Sector Classifications:
Related Grants:
Panel History:  
Summary on Grant Application Form
Many computational problems involve search. For example, we may need to search for the best time-table for staff in a school or hospital. It is often worth investing a great amount of effort in solving such problems as an optimal or near-optimal solution can be of considerable economic value. The hardest computational problems tend to occur where problems are neither obviously under- constrained nor obviously over- constrained. We have recently proposed a definition of the constrainedness of computational problems. This project has two aims. First, can this definition of constrainedness predict the location of hard computational problems in a wide variety of domains? Second, can we improve the performance of algorithms as a consequence? For example, given a choice of representations for a problem, do we prefer the least or most constrained? This project is both very novel and timely, unifying work performed in isolation in several different domains. It will result in better algorithms and heuristics for a wide variety of problems. In addition, it will greatly improve our knowledge about what makes computational problems hard. The applicants are at the cutting edge of research in this area. The area itself is attracting significant attention internationally.
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.strath.ac.uk