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.

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

项目成果

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