EPSRC logo

Details of Grant 

EPSRC Reference: EP/W014750/1
Title: New Techniques for Resolving Boundary Problems in Total Search
Principal Investigator: Fearnley, Dr J
Other Investigators:
Savani, Professor R
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 DatePanel NameOutcome
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
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
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