New Directions in Proof Complexity and Communication Complexity

点击翻译按钮获取中文摘要

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.