AF: Small: Computational Complexity Theory and Circuit Complexity

一些计算问题比其他问题需要更多的资源。 但是，识别哪些计算问题是困难的，哪些是容易的，这是非常具有挑战性的。 从以下意义上讲，它也是极其重要的。 我们的经济在很大程度上依赖于安全的在线金融交易，而公钥加密是提供在线安全的重要组成部分。 然而，每一个公钥密码系统都依赖于某种函数的存在，这种函数很容易计算，但很难求逆（所谓的单向函数）。 尽管经过了半个世纪的共同努力，单向函数是否存在仍然是未知的。 相反，计算复杂性理论领域已经成功地开发了一个框架，用于理解各种问题如何相互关联。 这个框架包括一个集合的“复杂性类”和概念的“减少”之间的计算问题。 这是一个令人惊讶的经验观察，在实践中遇到的绝大多数计算问题可以有他们的计算复杂性，这些类的精确特征。 即：两个问题被认为是“等价的”，如果每一个问题都可以简化为另一个问题，使得一个问题的有效算法产生另一个问题的有效算法。在实践中出现的大多数计算问题在这个意义上都等价于某个复杂性类中的“最难”问题。 因此，理解现实世界的计算问题的复杂性归结为理解各种复杂性类之间的关系。本项目旨在通过使用“元复杂性”的方法来提高我们对复杂性类之间关系的理解。 复杂性理论的重点是确定问题的难度。元复杂性的重点是确定问题有多难。 最小电路尺寸问题（Minimum Circuit Size Problem，MCSP）：给定布尔函数的真值表，确定计算该函数的最小电路的尺寸。 最近的工作表明，在我们对MCSP复杂性的理解方面，即使有微小的改进，也会在回答长期存在的关于复杂性类别之间关系的开放性问题方面产生巨大的影响。 该项目将寻求建立在最近的工作，以建立一个更清晰的画面MCSP如何适应复杂性类的框架，在计算复杂性理论的其他调查。这个奖项反映了NSF的法定使命，并已被认为是值得的支持，通过评估使用基金会的智力价值和更广泛的影响审查标准。

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.