New Directions in Proof Complexity and Communication Complexity

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

• 批准号: 228106-2012
• 负责人: Pitassi, Toniann
• 金额: $ 5.68万
• 依托单位: University of Toronto
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2015
• 资助国家: 加拿大
• 起止时间: 2015-01-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=570353
• 关键词: 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. One promising direction aimed at ultimately resolving the P versus NP question is propositional proof complexity. The central problem in propositional proof complexity is to understand which tautologies have efficient proofs in standard proof systems. Cook and Reckhow observed in 1974 that the question of whether there is a proof system giving rise to short proofs of all tautologies is equivalent to whether NP equals coNP, and therefore is closely connected to the P versus NP question. Proof complexity also gives a methodology for understanding natural classes of algorithms for solving NP-hard problems. I propose to develop methods for proving lower bounds for various proof systems and classes of algorithms, and to use these methods to obtain new insight and new lower bounds and inapproximability results for realistic models of computation. A fundamental tool in this endeavor is communication complexity; thus new communication models and techniques are a key aspect of this proposal.

计算复杂性的核心问题是理解哪些计算问题可以有效地解决，并为这些问题开发最有效的算法。NP完全问题是否有有效的解决方案的问题，被称为P与NP问题，是我研究背后的驱动力。这是一个美丽而深刻的问题，它的解决将产生深远的影响。 一个有希望的方向，旨在最终解决P与NP问题是命题证明的复杂性。命题证明复杂性的中心问题是理解哪些重言式在标准证明系统中具有有效的证明。库克和雷克豪在1974年观察到，是否存在一个证明系统来产生所有重言式的简短证明的问题等价于NP是否等于coNP，因此与P对NP问题密切相关。证明复杂性还提供了一种方法来理解解决NP难问题的算法的自然类。 我建议开发的方法证明各种证明系统和算法类的下界，并使用这些方法来获得新的见解和新的下界和不可逼近的结果，为现实的计算模型。在这奋进的一个基本工具是通信的复杂性，因此新的通信模型和技术是这个建议的一个关键方面。