EAGER: AF: New approaches to hardness for circuit minimization

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

The goal of this activity is to understand the structure of complexity classes.  Complexity classes provide the best tool currently available for understanding the computational complexity of real-world computational problems.  Some of these problems are notoriously difficult, but recent progress justifies some optimism that additional useful insight about these complexity classes can be obtained.The Minimum Circuit Size Problem (MCSP) is a well-known example of an apparently-intractable problem in NP that is not widely believed to be NP-complete.  Until now, all of the evidence that has been gathered -- trying to indicate that MCSP is hard to compute -- has followed the same path, invoking the connections between derandomization techniques and cryptographically-secure one-way functions.  This proposal will focus on developing a direct approach to reduce seemingly-hard problems to MCSP, and thereby set the stage for a more thorough understanding of the complexity of MCSP. The research results will be broadly disseminated, both through journal publications as well as through survey articles in various venues. The long-term goals of research in computational complexity, if finally achieved, will have profound impact on society (for instance, by providing firm mathematical underpinnings to public-key cryptography, which currently rests upon many unproven conjectures).