EAGER: AF: New approaches to hardness for circuit minimization

EAGER：AF：电路最小化硬度的新方法

• 批准号: 1555409
• 负责人: Eric Allender
• 金额: $ 10万
• 依托单位: Rutgers University New Brunswick
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2017-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1555409&HistoricalAwards=false
• 关键词: EAGER; AF; New; approaches; hardness

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).

本活动的目标是理解复杂性类的结构。复杂性类提供了目前可用于理解现实世界计算问题的计算复杂性的最佳工具。其中一些问题是众所周知的困难，但最近的进展证明了一些乐观的看法，即可以获得关于这些复杂性类别的额外有用的见解。最小电路尺寸问题（MCSP）是一个很好的，已知的NP中一个明显棘手的问题的例子，但人们并不普遍认为它是NP完全的。到目前为止，所有已经收集到的证据--试图表明MCSP很难计算--都遵循着同样的路径，调用去随机化技术和加密安全技术之间的联系，本提案将侧重于制定一种直接的办法，减少小额信贷社区支助方案难以解决的问题，从而为更透彻地了解小额信贷社区支助方案的复杂性奠定基础。 研究结果将通过期刊出版物和在各种场合发表的调查文章广泛传播。计算复杂性研究的长期目标如果最终实现，将对社会产生深远的影响（例如，通过为公钥密码学提供坚实的数学基础，目前公钥密码学依赖于许多未经证实的假设）。

项目成果

The Minimum Oracle Circuit Size Problem

• DOI: 10.1007/s00037-016-0124-0
• 发表时间: 2016-02
• 期刊: computational complexity
• 影响因子: 1.4
• 作者: Eric Allender;D. Holden;Valentine Kabanets