New Techniques for Resolving Boundary Problems in Total Search

多项式时间算法是理论计算机科学中最核心的概念之一，因为多项式时间可解性是被认为是可处理的问题和不能被计算机有效地解决的问题之间的分界线。计算复杂性领域研究这种区别，目的是对问题进行分类：要么通过为问题找到非多项式时间算法来表明问题是可处理的，要么通过证明困难的结果来表明问题不太可能是可处理的。NP-完备性的概念是展示困难结果的最著名的工具之一。如果一个问题被证明是NP-难的，那么除非NP中的每个问题都能在多项式时间内求解，否则就不可能有一个多项式时间算法。NP-完备性的概念已经取得了很大的成功，现在已经有数百个重要的问题被认为是NP-完全的，然而，NP-硬度并不是适用于每一个问题。在这个提案中，我们研究总的搜索问题，这些问题总是保证有解决方案。有充分的理论理由相信，没有完全搜索问题是NP难的，这导致了其他用于表示完全搜索问题的难度的理论工具的发展，这些工具已经被成功地应用于表明许多完全搜索问题是困难的。尽管如此，仍然有非常重要的完全搜索问题尚未得到解决。对于这些问题，我们没有多项式时间算法，但我们也没有令人信服的困难证据。我们称这些边界问题为边界问题，因为它们位于我们所知的多项式时间可解性的边界上。在这个提案中，我们研究了各种应用领域感兴趣的突出边界问题，包括形式验证、优化和机器学习以及算法博弈论。我们的中心目标是解决这些问题的边界状态，要么证明它们是困难的，要么通过找到一个新的多项式时间算法来解决它们。

Polynomial-time algorithms are one of the most central concepts in TheoreticalComputer Science, because polynomial-time solvability is thedividing line between problems that are considered to be tractable, meaning thatthey can be solved efficiently by a computer, and those that are not. The field of Computational Complexity studies this distinction, with the goal ofclassifying problems: either showing that a problem is tractable by finding apolynomial-time algorithm for it, or showing that the problem is unlikely to betractable by proving a hardness result. The concept of NP-completeness is one of the most well known tools for showinghardness results. If a problem is shown to be NP-hard, then there cannot be apolynomial-time algorithm for it unless every problem in NP can be solved inpolynomial time, which is considered to be unlikely. The concept ofNP-completeness has been highly successful, and there are now hundreds ofimportant problems that are known to be NP-complete.However, NP-hardness cannot be applied to every problem. In this proposal westudy total search problems, which are problems that are always guaranteed tohave a solution. There are good theoretical reasons to believe that no totalsearch problem can be NP-hard, and this has led to the development of othertheoretical tools for showing hardness for total search problems (likePPAD-hardness and PLS-hardness), which have been successfully applied toshow that many total search problems are hard.Despite this, there are still extremely important total search problems whosestatus is unresolved. We have no polynomial-time algorithm for these problems,but we also have no convincing evidence of hardness either. We callthese boundary problems, because they lie on the boundary of our knowledge aboutpolynomial-time solvability. In this proposal we study prominent boundary problems that are of interest to avariety of application areas, including Formal Verification, Optimization andMachine Learning, and Algorithmic Game Theory. Our central aim is to resolve theboundary status of these problems, by either showing that they are hard, or byfinding a new polynomial-time algorithm for solving them.