New Techniques for Resolving Boundary Problems in Total Search

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

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.