AF: Small: Computational Complexity Theory and Circuit Complexity

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

Some computational problems require more resources than others. But recognizing which computational problems are hard and which are easy turns out to be extremely challenging. It also turns out to be extremely important, in the following sense. Much of our economy relies on secure on-line financial transactions, and public-key cryptography is an essential component of providing on-line security. However, every public-key cryptographic system relies on the existence of some function that is easy to compute and hard to invert (a so-called one-way function). Despite a half-century of concerted effort, it remains unknown if one-way functions exist. Instead, the field of computational complexity theory has succeeded in developing a framework for understanding how various problems relate to each other. This framework consists of a collection of "complexity classes" and notions of "reductions" among computational problems. It is a surprising empirical observation that the overwhelming majority of computational problems that are encountered in practice can have their computational complexity precisely characterized in terms of these classes. That is: two problems are considered to be "equivalent" if each can be reduced to the other, so that an efficient algorithm for one yields an efficient algorithm for the other. Most computational problems that arise in practice turn out to be equivalent in this sense to a "hardest" problem in some complexity class. Thus, understanding the complexity of real-world computational problems boils down to understanding the relationships among various complexity classes.This project seeks to improve our understanding of the relationships among complexity classes by using the approach of "metacomplexity". The focus of complexity theory is to determine how hard problems are. The focus of metacomplexity is to determine how hard it is to determine how hard problems are. The canonical example of a problem in metacomplexity is the Minimum Circuit Size Problem (MCSP): given the truth table of a Boolean function, determine the size of the smallest circuit computing the function. Recent work has shown that seemingly-slight improvements in our understanding of the complexity of MCSP would have dramatic consequences in terms of answering long-standing open questions about the relationships among complexity classes. The project will seek to build on this recent work, in order to establish a clearer picture of how MCSP fits into the framework of complexity classes, among other investigations in computational complexity theory.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.