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

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.