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

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

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.