AF: Medium: Research in Algorithms and Complexity for Total Functions

为实际计算问题寻找有效的算法从80年前开始就定义了计算机科学。同样重要的是寻找难解性，也就是说，确定某些计算任务不能有效地解决。在过去的半个世纪里，NP完备性的重要概念在将实际问题划分为可处理的和难以处理的方面取得了长足的进步，模化了尚未解决的P / NP问题。这个项目将解决最重要的计算问题，这些问题不能如此分类，即一类问题，其中寻求某种解决方案，并且解决方案保证存在。令人惊讶的是，尽管解决方案的存在似乎使问题变得容易，但仍有许多这类重要的计算问题无法理解有效的可解性。此外，相当重要的是，其中一些问题的明显困难在于现代密码学的基础。在20世纪80年代和90年代帮助发起这一研究路线的研究人员将解决这一领域的许多新旧开放问题。特别是，调查人员应研究一些与全函数有关的开放性复杂性问题，包括塔斯基不动点的复杂性；未分类组合问题，推广鸽洞原理类PPP；关于全函数与密码学的新复杂性问题，以及他们在研究APEPP类过程中产生的复杂性的一些基本问题。他们还将探讨黑箱算法在TFNP问题中的能力和局限性。关键词:算法;复杂性;总功能。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Finding efficient algorithms for practical computational problems has defined computer science from its beginnings almost eight decades ago. Equally fundamental has been the search for intractability, that is, establishing that certain computational tasks cannot be solved efficiently. The important concept of NP-completeness has come a long way over the past half century in classifying practical problems into tractable and intractable, modulo the yet unresolved P vs NP question. This project will address the most important body of computational problems which cannot be so classified, namely the class of problems in which a solution of certain kind is sought, and the solution is guaranteed to exist. Surprisingly, even though the existence of a solution may appear to render a problem easy, there are many important computational problems of this sort for which efficient solvability is not understood. In addition, and quite importantly, the apparent difficulty of some of these problems lies at the foundations of modern Cryptography. The investigators, who helped initiate this line of research in the 1980s and 1990s, will address many old and new open questions in this field.In particular, the investigators shall pursue a number of open complexity questions related to total functions including the complexity of Tarski fixpoints; unclassified combinatorial problems, generalizing the pigeonhole principle class PPP; new complexity problems relating total functions with Cryptography, as well as certain fundamental problems in Complexity that arose from their study of the class APEPP. They shall also explore the power and limitations of black box algorithms for TFNP problems. Keywords: Algorithms; complexity; total functions.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.