AF: Small: Computational Complexity Theory and Circuit Complexity

AF：小：计算复杂性理论和电路复杂性

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

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.

一些计算问题需要比其他计算问题更多的资源。 但是认识到哪些计算问题很难，哪些很容易被证明是极具挑战性的。 从以下意义上讲，这也非常重要。 我们的大部分经济都依赖于安全的在线金融交易，而公钥加密是提供在线安全性的重要组成部分。 但是，每个公共密钥系统都依赖于某些易于计算且难以倒转的功能的存在（所谓的单向功能）。 尽管有半个世纪的努力，但是否存在单向功能，仍然未知。 取而代之的是，计算复杂性理论的领域成功地开发了一个框架，以了解各种问题之间的关系。 该框架包括一系列“复杂性类别”和计算问题中“减少”的概念。 令人惊讶的经验观察是，在实践中遇到的绝大多数计算问题可以使其计算复杂性精确地以这些类别的形式来表征。 也就是说：如果每个问题都可以减少到另一个问题，则认为两个问题是“等效的”，因此一个有效的算法可以使另一个问题产生有效的算法。实际上，在这种意义上，大多数计算问题与某些复杂性类别中的“最困难”问题相同。 因此，理解现实世界中计算问题的复杂性归结为理解各种复杂性类别之间的关系。该项目旨在通过使用“ metacomplexity”的方法来提高我们对复杂性类别之间关系的理解。 复杂性理论的重点是确定问题有多严重。 Metacomplexity的重点是确定确定问题的难度。 元素复合度问题的规范示例是最小电路尺寸问题（MCSP）：鉴于布尔函数的真实表，请确定计算函数的最小电路的大小。 最近的工作表明，在回答有关复杂性阶级之间关系的长期开放问题方面，我们对MCSP复杂性的理解看似改善将产生巨大的后果。 该项目将寻求基于这项最近的工作，以便更清楚地了解MCSP如何适应复杂性类别的框架，以及计算复杂性理论中的其他调查。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的审查标准通过评估来通过评估来支持的。

项目成果

Depth-first search in directed planar graphs, revisited

重新审视有向平面图中的深度优先搜索

• DOI: 10.1007/s00236-022-00425-1
• 发表时间: 2022
• 期刊: Acta Informatica
• 影响因子: 0.6
• 作者: Allender, Eric;Chauhan, Archit;Datta, Samir
• 通讯作者: Datta, Samir

Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

• DOI: 10.53733/148
• 发表时间: 2021-09
• 期刊: New Zealand Journal of Mathematics
• 作者: Eric Allender

One-Way Functions and a Conditional Variant of MKTP

单向函数和 MKTP 的条件变体

• DOI: 10.4230/lipics.fsttcs.2021.7
• 发表时间: 2021
• 期刊: Leibniz international proceedings in informatics
• 作者: Allender, Eric;Cheraghchi, Mahdi;Myrisiotis, Dimitrios;Tirumala, Harsha;Volkovich, Ilya
• 通讯作者: Volkovich, Ilya

The Non-Hardness of Approximating Circuit Size

近似电路尺寸的非困难性

• DOI: 10.1007/978-3-030-19955-5_2
• 发表时间: 2021
• 期刊: Theory of computing systems
• 影响因子: 0.5
• 作者: Allender, Eric;Ilango, Rahul;Vafa, Neekon
• 通讯作者: Vafa, Neekon

Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity

Ker-I Ko 与资源有限 Kolmogorov 复杂性研究

• DOI: 10.1007/978-3-030-41672-0_2
• 发表时间: 2020
• 期刊: Lecture notes in computer science
• 作者: Allender, Eric