权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

New Techniques for Resolving Boundary Problems in Total Search

解决全搜索中边界问题的新技术

基本信息

批准号：
EP/W014750/1
负责人：
John Fearnley
金额：
$ 56.23万
依托单位：
University of Liverpool
依托单位国家：
英国
项目类别：
Research Grant
财政年份：
2023
资助国家：
英国
起止时间：
2023 至无数据
项目状态：
未结题

来源：
https://gtr.ukri.org/projects?ref=EP%2FW014750%2F1
关键词：
New Techniques Resolving Boundary Problems

项目摘要

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.

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