AF: Medium: Computational Complexity Theory and Circuit Complexity

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

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.