Newsgroups: ont.events,ut.dcs.seminars,ut.dcs.theory
From: edith@cs.toronto.edu (Edith Fraser)
Subject: Madhan Sudan, Tuesday 21 April 1992: THEORY
Date: 13 Apr 92 15:31:22 GMT


           Department of Computer Science, University of Toronto
              (GB = Galbraith Building, 35 St. George Street)

       -------------------------------------------------------------

                                  THEORY
                GB119, at 11:00 a.m., Tuesday 21 April 1992

                               Madhan Sudan
                   University of California at Berkeley

             "On the Intractability of Approximation Problems"

While the notion of P vs. NP provides a very nice framework to study the
exact solutions to optimization problems, it seems to lack sufficient
structure to study the hardness of finding approximate solutions to
optimization problems. This inadequacy is apparent from the fact that some
NP complete optimization problems (e.g., bin packing) have simple
algorithms for finding very good approximate solutions, while other
problems have been extremely hard to approximate (e.g., approximating the
chromatic number, the clique size etc.)

A nice framework for studying the tractability of approximate solutions was
proposed recently by Papadimitriou and Yanakakis, where they define a class
MAX SNP, which contains a large number of very natural problems from NP,
with the property that the solution to all of these problems can be
approximated to  some constant factor. Moreover, they exhibit that some
very natural problems are complete or hard for the class, in the sense that
if the solution to any of these problems can be approximated to {\m
arbitrarily} small constant factors, then the optimum solution to any
problem in the class can be approximated to arbitrarily small constant
factors. A list of interesting problems hard for this class includes MAX
3SAT, TSP on metric spaces, Vertex Cover, Steiner Tree Problem, shortest
superstring etc.  The question of whether such approximation schemes could
be found for the complete problems in this class was left unresolved.

In this talk, we show that the maximum number of satisfiable clauses in a
3-SAT formula (MAX 3SAT) CANNOT be approximated to arbitrarily small
constants (unless NP=P) thus resolving the open question of [PY]. This
immediately shows the hardness of finding good approximate solutions to all
the problems listed above. Our results also show the following:

        1) No polynomial time algorithm can approximate the maximum
           clique size within a factor of n^epsilon, for some epsilon>0,
           unless NP=P. (via a recent result of Feige et. al. [FGLSS])

        2) No polynomial time algorithm for approximating longest paths
           can achieve {\m any} constant ratio (unless NP=P).

The hardness results above follow as a consequence of the following Result
which might be of independent interest as an alternate characterization of
NP: "All languages in NP have proofs of membership that can be

probabilistically verified very efficiently. In particular examining only a
constant number of randomly chosen bits of the proof suffices to obtain a
probabilistic guarantee of its correctness."

Joint work with Sanjeev Arora, Carsten Lund, Rajeev Motwani and Mario
Szegedy.