From: stevena@cory.Berkeley.EDU (Steven Alexander)
Subject: On the Intractability of Approximation Problems
Keywords: NP, approximation
Organization: University of California, at Berkeley
Date: Sat, 11 Apr 1992 04:25:53 GMT


Date: Fri, 10 Apr 92 08:33:13 -0700
From: liza@hera.berkeley.edu (Liza C. Gabato)
To: seminar@hera.berkeley.edu
Subject: CS Division, U.C.B. Seminar(s) for the month of April

                          CS 298-2
                       Theory Seminar

                        Madhu Sudan
                      Graduate Student
          Computer Science Division, U.C. Berkeley

      On the Intractability of Approximation Problems

                   Monday, April 13, 1992
                   4:00 p.m. - 5:30 p.m.
                        5 Evans Hall


     While the notion of P  vs.  NP  provides  a  very  nice
framework to study the exact solutions to optimization prob-
lems, 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 con-
tains  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  con-
stant  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 ques-
tion 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 satis-
fiable  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 long-
     est  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 ver-
ified very efficiently. In particular examining only a  con-
stant  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.