| EPSRC Reference: |
EP/W014750/1 |
| Title: |
New Techniques for Resolving Boundary Problems in Total Search |
| Principal Investigator: |
Fearnley, Dr J |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Liverpool |
| Scheme: |
Standard Research |
| Starts: |
01 January 2023 |
Ends: |
31 December 2025 |
Value (£): |
441,269
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Software Engineering |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
| Panel Date | Panel Name | Outcome |
|
18 Jan 2022
|
EPSRC ICT Prioritisation Panel January 2022
|
Announced
|
|
|
Summary on Grant Application Form |
Polynomial-time algorithms are one of the most central concepts in Theoretical
Computer Science, because polynomial-time solvability is the
dividing line between problems that are considered to be tractable, meaning that
they can be solved efficiently by a computer, and those that are not.
The field of Computational Complexity studies this distinction, with the goal of
classifying problems: either showing that a problem is tractable by finding a
polynomial-time algorithm for it, or showing that the problem is unlikely to be
tractable by proving a hardness result.
The concept of NP-completeness is one of the most well known tools for showing
hardness results. If a problem is shown to be NP-hard, then there cannot be a
polynomial-time algorithm for it unless every problem in NP can be solved in
polynomial time, which is considered to be unlikely. The concept of
NP-completeness has been highly successful, and there are now hundreds of
important problems that are known to be NP-complete.
However, NP-hardness cannot be applied to every problem. In this proposal we
study total search problems, which are problems that are always guaranteed to
have a solution. There are good theoretical reasons to believe that no total
search problem can be NP-hard, and this has led to the development of other
theoretical tools for showing hardness for total search problems (like
PPAD-hardness and PLS-hardness), which have been successfully applied to
show that many total search problems are hard.
Despite this, there are still extremely important total search problems whose
status is unresolved. We have no polynomial-time algorithm for these problems,
but we also have no convincing evidence of hardness either. We call
these boundary problems, because they lie on the boundary of our knowledge about
polynomial-time solvability.
In this proposal we study prominent boundary problems that are of interest to a
variety of application areas, including Formal Verification, Optimization and
Machine Learning, and Algorithmic Game Theory. Our central aim is to resolve the
boundary status of these problems, by either showing that they are hard, or by
finding a new polynomial-time algorithm for solving them.
|
|
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 |