New Techniques for Resolving Boundary Problems in Total Search

点击翻译按钮获取中文摘要

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.