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很难计算 - 遵循了相同的路径，从而调用了降低的技术和密码确定的单向函数之间的连接。该提案将着重于开发一种直接方法，以减少MCSP看似危险的问题，从而为更彻底地了解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