ADMISSIONS| ACADEMICS| SWARTHMORE

Talk by Toniann Pitassi, University of Toronto

Proof complexity and inapproximability results for NP-complete problems
Tuesday, Mar 27 2007
4:15 pm in Science Center 199

Abstract

Cook's famous NP-completeness theorem in the 1970's shows that a variety of fundamental NP-complete problems are essentially equivalent in the sense that any one of them has an efficient algorithm if and only if all of them are tractable. Since all NP-complete problems are believed to be intractable, a focus in the last few decades has been to discover efficient algorithms that are "approximately" correct. To illustrate, consider the well-studied vertex cover problem. The input is an undirected graph G=(V,E), and the output should be a subset S of vertices of minimal size, such that for every edge (i,j) in the graph, either i or j is in S. While finding the absolute smallest such set S is NP-hard, there is a simple greedy algorithm that will output a vertex cover of size at most two times the smallest vertex cover. On the other hand, a beautiful theorem of Dinur and Safra shows that computing a vertex cover S' of size within a factor of 1.36 of the smallest vertex cover is as hard as computing the smallest vertex cover itself! This theorem, as well as "inapproximability results" for other NP-hard problems, is a direct result of the discovery of the PCP theorem in the 1980's, which has revolutionized our understanding of the approximability of most NP-hard optimization problems.

In this talk, we will first give a brief survey of the PCP theorem, and how it has been used to prove inapproximability results for many fundamental NP-hard optimization problems. We will then discuss several important problems whose exact inapproximability status is still unresolved. The vertex cover problem mentioned above is one of the outstanding open problems in the complexity of approximation. The best known approximation is a factor of 2, whereas the best inapproximability result of Dinur and Safra shows that it is NP hard to solve the problem within a factor of 1.36.

To get a better picture of the approximability of vertex cover, and other NP-hard problems whose approximability status has not been resolved using PCP-based methods, we will explore attempts based on proof complexity to rule out good approximations for vertex cover (and related problems) by large families of algorithms. The central idea is that each natural propositional proof system gives rise to a corresponding family of algorithms whose correctness proof is formalizable in the proof system. For vertex cover, the most important proof systems are so-called "cutting planes proof systems", and the natural algorithms underlying these proof systems include essentially all relaxations of semi-definite programming (SDP) algorithms that have been used to approximate NP-hard problems.

We will survey what is currently known, and present a new result showing that the integrality gap for vertex cover is 2-o(1), even after sqrt(logn/loglogn) rounds of the the SDP LS+ system of Lovasz and Schriver. The new results discussed in the talk are joint work with Konstantinos Georgiou, Avner Magen, and Iannis Tourlakis.