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.

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

项目成果

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