Foundations of Complexity Theory

复杂性理论的基础

• 批准号: 0310466
• 负责人: Boaz Barak
• 金额: --
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-06-01 至 2007-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0310466&HistoricalAwards=false
• 关键词: Foundations; Complexity; Theory

Complexity theory addresses the question of how much resource is needed to solve a given computational problem. In recent years complexity theory has found connections and applications in many scientific and engineering disciplines. This project plans to investigate complexity theory across a broad front. The topics include communication complexity, decision trees, quantum algorithms, quantum cryptography, and other foundational issues in complexity theory. Te goal is to gain deep insights into the nature of computation, so that one can most effectively perform computational tasks in any model. It is expected that a variety of algebraic and combinatorial techniques will be called upon to explore these topics.Two of the most interesting scientific developments in recent years spring from the realization that complexity theory can be utilized for cryptography, and that quantum mechanics can be used for performing powerful computation. Advances in these fronts have attracted interest from scientific communities at large, as their relevance is far-reaching. The research of this project could lead to substantial further progress in these two areas.In the broader domain of public education, the Principal Investigator has given many speeches in recent years on various topics on complexity, cryptography and quantum computing. Many of these talks are geared toward general audiences and often undergraduate students. These lectures, if thoughtfully designed, can stimulate the intellectual curiosity of young minds and develop their interest in the computing sciences. With further advances of research in these areas, one can expect that public awareness and interest will be further enhanced to the good of a stronger scientific education.

复杂性理论解决了解决给定计算问题需要多少资源的问题。 近年来，复杂性理论在许多科学和工程学科中找到了联系和应用。 该项目计划广泛研究复杂性理论。 主题包括通信复杂性、决策树、量子算法、量子密码学以及复杂性理论中的其他基础问题。 我们的目标是深入了解计算的本质，以便人们可以在任何模型中最有效地执行计算任务。 预计将调用各种代数和组合技术来探索这些主题。 近年来两个最有趣的科学发展源于这样的认识：复杂性理论可以用于密码学，并且量子力学可以用于执行强大的计算。 这些领域的进展引起了整个科学界的兴趣，因为它们的相关性是深远的。 该项目的研究可能会在这两个领域带来实质性的进一步进展。 在更广泛的公共教育领域，首席研究员近年来就复杂性、密码学​​和量子计算等各种主题发表了多次演讲。 其中许多讲座面向普通观众，通常是本科生。 这些讲座如果经过精心设计，可以激发年轻人的求知欲，培养他们对计算科学的兴趣。 随着这些领域研究的进一步进展，可以预期公众的意识和兴趣将进一步增强，有利于加强科学教育。