Special Year in Computational Complexity Theory

计算复杂性理论特别年

• 批准号: 9987077
• 负责人: Avi Wigderson
• 金额: $ 30万
• 依托单位: Institute For Advanced Study
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-09-01 至 2001-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9987077&HistoricalAwards=false
• 关键词: Special; Year; Computational; Complexity; Theory

Avi Wigderson9987077This project will support three senior researchers to participate in a special year on computational complexity theory at the Institute for Advanced Studies. These researchers will attract the participation of other top researchers in computational complexity. Computational complexity theory has opened up one of the most exciting fields of scientific and mathematical research over the last 20 years, with dramatic achievements and fundamental understandings appearing at a high rate. One obvious explanation for the recent progress in this field is that this research is guided by a few clear and focused questions, deeply motivated on scientific, practical and philosophical grounds. The most central of these are:P=NP?, or more generally, are the many natural computational problems we can't solve really difficult?NP=coNP?, or more generally, what constitutes a difficult theorem to prove:P=BPP?, or more generally, does randomization really help efficient computation?BPP=QP?, or more generally, can quantum mechanics be efficiently simulated classically?Resolving any of these questions is clearly very long term goal, but each has stimulated the development of concepts, problems, proof techniques and results which start paving a path towards a possible resolution.But what really characterized the progress, and explained much of the successes so far, was the unveiling of many rich and beautiful connections between the sets of concepts and sub-problems each of these major questions gave rise to. There is little doubt that such connections are, and will be, the foundation for understanding the major questions of complexity theory. Indeed, these connections are what is making the complex world of computational complexity into a theory. The focus of this special year at the Institute will be to better understand these connections and their implications, to unify and extend them, and to look for new ones.

Avi Wigderson9987077该项目将支持三名高级研究人员参加高级研究所计算复杂性理论的特殊年份。 这些研究人员将吸引其他顶级研究人员参与计算复杂性。计算复杂性理论在过去20年中开辟了最令人兴奋的科学和数学研究领域之一，其成就和基本理解的出现很高。 对该领域最近进步的一个明显的解释是，这项研究以一些明确而重点的问题为指导，深深地激发了科学，实用和哲学的基础。 其中最重要的是：p = np？，或更普遍地，我们无法真正难以解决的许多自然计算问题吗？刺激了概念，问题，证明技术和结果的发展，这些概念，问题，证明技术和结果开始铺平了可能的解决方案的道路。但是，真正表征了进步的方法，并解释了到目前为止的许多成功，这是揭开了许多概念和子问题之间的许多丰富而美丽的联系，这些主要问题都引起了人们的注意。 毫无疑问，这种联系是理解复杂性理论的主要问题的基础。 确实，这些联系是使计算复杂性复杂世界变成理论的原因。 该研究所的特殊年份的重点将是更好地了解这些联系及其含义，以统一和扩展它们，并寻找新的联系。