New Directions in Proof Complexity and Communication Complexity

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

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.