AF: Medium: Computational Complexity Theory and Circuit Complexity

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

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

This award focuses on problems in computational complexity theory, with the goal of clarifying the power and limitations of various important classes of algorithms (known as "complexity classes"). Complexity classes provide the best tools currently available for understanding the computational complexity of real-world computational problems. Part of the award supports a collaboration with researchers at the Czech Academy of Sciences.Kolmogorov complexity measures the amount of "information" in a finite string, and also provides a mathematical definition of what it means for a string to be "random". Although the Kolmogorov complexity of an arbitrary string cannot be computed, there are strong connections between the (non-computable) notion of randomness and questions about the circuit size required to compute various functions. This award will support an investigation into recent indications that computational complexity classes can be characterized in terms of efficient access to the Kolmogorov complexity function, thus possibly opening a new portal for techniques from the theory of computability and algorithmic randomness to be applied in complexity theory. The award will also support an investigation into the limits of computation by arithmetic circuits. (In an arithmetic circuit, data can only be manipulated by arithmetic operations such as addition and multiplication; operations that directly access the individual bits of numeric data are not supported.)The long-term goals of research in computational complexity, if finally achieved, will have profound impact on the society---for instance, by providing firm mathematical underpinnings to public-key cryptography, which currently rests upon many unproven conjectures. This research activity offers concrete plans for incremental progress toward this long-range goal. The award also supports graduate education. As such, it will assist with training new researchers and educators. The research results will be broadly disseminated, not only through journal publication but also through survey articles in various venues.

该奖项重点关注计算复杂性理论中的问题，旨在阐明各种重要算法类别（称为“复杂性类别”）的能力和局限性。 复杂性类提供了当前可用于理解现实世界计算问题的计算复杂性的最佳工具。 该奖项的一部分是支持与捷克科学院研究人员的合作。柯尔莫哥洛夫复杂度衡量有限字符串中的“信息”量，并且还提供了字符串“随机”含义的数学定义。 尽管无法计算任意字符串的柯尔莫哥洛夫复杂度，但（不可计算的）随机性概念与计算各种函数所需的电路大小问题之间存在着密切的联系。 该奖项将支持对最近迹象的调查，即计算复杂性类别可以通过有效访问柯尔莫哥洛夫复杂性函数来表征，从而可能为可计算性和算法随机性理论中的技术应用于复杂性理论打开一个新的门户。 该奖项还将支持对算术电路计算极限的调查。 （在算术电路中，数据只能通过加法和乘法等算术运算来操作；不支持直接访问数字数据的各个位的操作。）计算复杂性研究的长期目标如果最终实现，将对社会产生深远的影响——例如，为公钥密码学提供坚实的数学基础，而公钥密码学目前依赖于许多未经证实的猜想。 这项研究活动为逐步实现这一长期目标提供了具体计划。 该奖项还支持研究生教育。 因此，它将有助于培训新的研究人员和教育工作者。 研究结果将被广泛传播，不仅通过期刊出版，而且通过在不同场所发表调查文章。

项目成果

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