Special Year in Computational Complexity Theory

Avi Wigderson9987077该项目将支持三名高级研究人员参加高级研究所计算复杂性理论的特殊一年。 这些研究人员将吸引计算复杂性领域其他顶尖研究人员的参与。在过去的20年里，计算复杂性理论开辟了科学和数学研究中最令人兴奋的领域之一，取得了巨大的成就和基本的理解。 对这一领域最近取得的进展的一个明显解释是，这项研究是由一些明确和集中的问题指导的，这些问题是基于科学、实践和哲学基础的。 其中最核心的是：P=NP？，或者更一般地说，我们无法解决的许多自然计算问题真的很难吗？NP=coNP？，或者更一般地说，什么构成了一个难以证明的定理：P=BPP？或者更一般地说，随机化真的有助于有效的计算吗？BPP=QP？，或者更一般地说，量子力学能被有效地经典模拟吗？解决这些问题显然是非常长期的目标，但每个都刺激了概念，问题，证明技术和结果的发展，开始为可能的解决铺平道路。但真正的特点是进展，并解释了迄今为止的大部分成功，是揭示了这些主要问题中的每个问题所产生的概念和子问题之间的许多丰富而美丽的联系。 毫无疑问，这种联系现在是，将来也将是理解复杂性理论主要问题的基础。 事实上，正是这些联系使计算复杂性的复杂世界成为一种理论。 研究所今年的重点是更好地理解这些联系及其影响，统一和扩展它们，并寻找新的联系。

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.