New Directions in Proof Complexity and Communication Complexity

证明复杂性和通信复杂性的新方向

• 批准号: 228106-2012
• 负责人: Pitassi, Toniann
• 金额: $ 5.68万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2014
• 资助国家: 加拿大
• 起止时间: 2014-01-01 至 2015-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=546884
• 关键词: New; Directions; Proof; Complexity; Communication

The central problem in computational complexity is to understand which computational problems can be solved efficiently, and to develop the most efficient algorithms for such problems. The question of whether the NP-complete problems have efficient solutions, known as the P versus NP question, is the driving force behind my research. It is a beautiful and deep question, and its solution would have profound consequences.

计算复杂性的核心问题是理解哪些计算问题可以有效地解决，并为这些问题开发最有效的算法。NP完全问题是否有有效的解决方案的问题，被称为P与NP问题，是我研究背后的驱动力。这是一个美丽而深刻的问题，它的解决将产生深远的影响。