New Techniques for Resolving Boundary Problems in Total Search

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.