WEBVTT
0-1:59:36,500 --> 0-1:59:36,580
0-1:59:36,580 --> 0-1:59:38,930
The following content is
provided under a Creative
0-1:59:38,930 --> 0-1:59:40,320
Commons license.
0-1:59:40,320 --> 0-1:59:42,560
Your support will help
MIT OpenCourseWare
0-1:59:42,560 --> 0-1:59:46,640
continue to offer high quality
educational resources for free.
0-1:59:46,640 --> 0-1:59:49,200
To make a donation or to
view additional materials
0-1:59:49,200 --> 0-1:59:53,100
from hundreds of MIT courses,
visit MIT OpenCourseWare
0-1:59:53,100 --> 0-1:59:53,763
at ocw.mit.edu.
0-1:59:53,763 --> 00:00:02,860
00:00:02.860 --> 00:00:06.630
PROFESSOR: So today is our
third and probably final lecture
00:00:06.630 --> 00:00:08.370
on approximation algorithms.
00:00:08.370 --> 00:00:11.260
We're going to take
a different approach
00:00:11.260 --> 00:00:15.840
to proving inapproximability
to optimization problems called
00:00:15.840 --> 00:00:16.950
gap problems.
00:00:16.950 --> 00:00:20.120
And we'll think about
gap-preserving reductions.
00:00:20.120 --> 00:00:24.180
We will prove along the way
optimal lower bound on Max 3SAT
00:00:24.180 --> 00:00:26.580
and other fun things.
00:00:26.580 --> 00:00:29.200
So let's start with
what a gap problem is.
00:00:29.200 --> 00:00:34.840
00:00:34.840 --> 00:00:37.250
I haven't actually seen a
generic definition of this,
00:00:37.250 --> 00:00:40.070
so this is new terminology,
but I think helpful.
00:00:40.070 --> 00:00:42.810
00:00:42.810 --> 00:00:46.920
A gap problem is a way of
converting an optimization
00:00:46.920 --> 00:00:49.180
problem into a decision problem.
00:00:49.180 --> 00:00:51.010
Now, we already know
one way to do that.
00:00:51.010 --> 00:00:53.090
If you have an NPO
optimization problem,
00:00:53.090 --> 00:00:55.190
you convert it into the
obvious decision problem,
00:00:55.190 --> 00:00:57.690
which is OPT at most k.
00:00:57.690 --> 00:01:02.100
For the minimization
problem, that is NP-complete.
00:01:02.100 --> 00:01:05.200
But we want to get something
useful from an approximability
00:01:05.200 --> 00:01:06.380
standpoint.
00:01:06.380 --> 00:01:11.690
And so the idea is, here's
a different problem.
00:01:11.690 --> 00:01:20.600
Instead of just deciding
whether OPT is at most k,
00:01:20.600 --> 00:01:25.810
we want to distinguish
between OPT being at most k
00:01:25.810 --> 00:01:33.860
versus OPT being at least
k over c for some value c.
00:01:33.860 --> 00:01:37.570
And the analogy here is with
c approximation algorithm,
00:01:37.570 --> 00:01:40.779
c does not have to be
constant, despite the name.
00:01:40.779 --> 00:01:41.820
Could be a function of n.
00:01:41.820 --> 00:01:43.100
Maybe it's log n.
00:01:43.100 --> 00:01:46.960
Maybe it's n to the
epsilon, whatever.
00:01:46.960 --> 00:01:50.806
So for a minimization
problem, normally--
00:01:50.806 --> 00:01:52.360
did I get this the right way?
00:01:52.360 --> 00:01:54.230
Sorry, that should be c times k.
00:01:54.230 --> 00:02:00.550
00:02:00.550 --> 00:02:04.330
For minimization and
for maximization,
00:02:04.330 --> 00:02:06.405
it's going to be the reverse.
00:02:06.405 --> 00:02:13.380
00:02:13.380 --> 00:02:18.530
And I think I'm going to use
strict inequality here also.
00:02:18.530 --> 00:02:20.090
So a minimization.
00:02:20.090 --> 00:02:23.250
There's a gap here
between k and c times k.
00:02:23.250 --> 00:02:28.140
We're imagining here
c is bigger than 1.
00:02:28.140 --> 00:02:30.456
So distinguishing
between being less than k
00:02:30.456 --> 00:02:35.820
and being at least c
times k leaves a hole.
00:02:35.820 --> 00:02:40.370
And the point is you
are promised that
00:02:40.370 --> 00:02:42.750
your input-- you
have a question?
00:02:42.750 --> 00:02:46.454
AUDIENCE: The second one,
should it really be c over k?
00:02:46.454 --> 00:02:50.225
00:02:50.225 --> 00:02:51.100
PROFESSOR: Sorry, no.
00:02:51.100 --> 00:02:54.040
00:02:54.040 --> 00:02:57.250
Thank you.
00:02:57.250 --> 00:03:02.271
c and k sound the same, so it's
always easy to mix them up.
00:03:02.271 --> 00:03:02.770
Cool.
00:03:02.770 --> 00:03:06.720
So the idea is that
you're-- so in both cases,
00:03:06.720 --> 00:03:10.240
there's a ratio gap here of c.
00:03:10.240 --> 00:03:12.080
And the idea is
that you're promised
00:03:12.080 --> 00:03:15.224
that your input falls into
one of these two categories.
00:03:15.224 --> 00:03:16.640
What does it mean
to distinguish--
00:03:16.640 --> 00:03:19.050
I mean, I tell you up
front the input either
00:03:19.050 --> 00:03:21.490
has this property
or this property,
00:03:21.490 --> 00:03:24.440
and I want you to
decide which one it is.
00:03:24.440 --> 00:03:28.110
And we'll call
these yes instances
00:03:28.110 --> 00:03:29.510
and these no instances.
00:03:29.510 --> 00:03:32.220
00:03:32.220 --> 00:03:33.730
Normally with a
decision problem,
00:03:33.730 --> 00:03:38.580
the no instance is that OPT is
just one bigger or one smaller.
00:03:38.580 --> 00:03:41.690
Now we have a big gap between
the no instances and the yes
00:03:41.690 --> 00:03:42.190
instances.
00:03:42.190 --> 00:03:43.700
We're told that that's true.
00:03:43.700 --> 00:03:45.330
This is called promise problem.
00:03:45.330 --> 00:03:49.060
00:03:49.060 --> 00:03:51.454
And effectively
what that means is
00:03:51.454 --> 00:03:53.329
if you're trying to come
up with an algorithm
00:03:53.329 --> 00:03:55.200
to solve this
decision problem, you
00:03:55.200 --> 00:03:58.220
don't care what the
algorithm does if OPT
00:03:58.220 --> 00:04:00.817
happens to fall in between.
00:04:00.817 --> 00:04:02.400
The algorithm can
do whatever it want.
00:04:02.400 --> 00:04:05.030
It can output digits
of pi in the middle,
00:04:05.030 --> 00:04:09.430
as long as when OPT is it
at most k or greater than
00:04:09.430 --> 00:04:11.560
or equal to k, it outputs yes.
00:04:11.560 --> 00:04:14.820
And when OPT is at least a
factor of c away from that,
00:04:14.820 --> 00:04:17.220
it outputs no.
00:04:17.220 --> 00:04:22.050
So that's an easier problem.
00:04:22.050 --> 00:04:32.590
And the cool thing is if the
c-gap version of a problem
00:04:32.590 --> 00:04:43.490
is NP-hard, then so
is c approximating
00:04:43.490 --> 00:04:44.480
the original problem.
00:04:44.480 --> 00:04:57.700
00:04:57.700 --> 00:05:00.840
So this really is in direct
analogy to c approximation.
00:05:00.840 --> 00:05:04.040
And so this lets us think
about an NP hardness
00:05:04.040 --> 00:05:08.250
for a decision problem and prove
an inapproximability result.
00:05:08.250 --> 00:05:10.450
This is nice because in
the last two lectures,
00:05:10.450 --> 00:05:15.540
we were having to keep track
of a lot more in just defining
00:05:15.540 --> 00:05:19.690
what inapproximability meant
and APX hardness and so on.
00:05:19.690 --> 00:05:22.174
Here it's kind of back
to regular NP hardnes.
00:05:22.174 --> 00:05:23.590
Now, the techniques
are completely
00:05:23.590 --> 00:05:27.300
different in this world than
our older NP hardness proofs.
00:05:27.300 --> 00:05:29.500
But still, it's kind of
comforting to be back
00:05:29.500 --> 00:05:32.670
in decision land.
00:05:32.670 --> 00:05:34.920
Cool.
00:05:34.920 --> 00:05:40.010
So because of this implication,
in previous lectures
00:05:40.010 --> 00:05:44.010
we were just worried about
proving inapproximability.
00:05:44.010 --> 00:05:46.610
But today we're
going to be thinking
00:05:46.610 --> 00:05:49.600
about proving that gap
problems are NP-hard,
00:05:49.600 --> 00:05:52.210
or some other kind of hardness.
00:05:52.210 --> 00:05:54.000
This is a stronger
type of result.
00:05:54.000 --> 00:05:56.020
So in general,
inapproximability is
00:05:56.020 --> 00:05:58.650
kind of what you care about
from the algorithmic standpoint,
00:05:58.650 --> 00:06:01.410
but gap results saying
that hey, your problem
00:06:01.410 --> 00:06:04.860
is hard even if you have
this huge gap between the yes
00:06:04.860 --> 00:06:06.740
instances and the
no instances, that's
00:06:06.740 --> 00:06:08.720
also of independent
interest, more
00:06:08.720 --> 00:06:10.870
about the structure
of the problem.
00:06:10.870 --> 00:06:11.990
But one implies the other.
00:06:11.990 --> 00:06:16.250
So this is the stronger
type of thing to go for.
00:06:16.250 --> 00:06:18.920
The practical reason to
care about this stuff
00:06:18.920 --> 00:06:24.050
is that this gap idea lets you
get stronger inapproximability
00:06:24.050 --> 00:06:25.150
results.
00:06:25.150 --> 00:06:29.050
The factor c you get by
thinking about gaps in practice
00:06:29.050 --> 00:06:32.570
seems to be larger
than the gaps you
00:06:32.570 --> 00:06:36.780
get by L reductions and things.
00:06:36.780 --> 00:06:41.610
So let me tell you about one
other type of gap problem.
00:06:41.610 --> 00:06:45.065
This is a standard one, a
little bit more precise.
00:06:45.065 --> 00:06:50.700
00:06:50.700 --> 00:06:52.420
Consider Max SAT.
00:06:52.420 --> 00:06:54.270
Pick your favorite
version of Max SAT,
00:06:54.270 --> 00:06:56.600
or Max CSP was the
general form where you
00:06:56.600 --> 00:06:58.640
could have any type of clause.
00:06:58.640 --> 00:07:01.265
Instead of just a c gap, we will
define slightly more precisely
00:07:01.265 --> 00:07:15.900
an a, b gap, which is to
distinguish between OPT
00:07:15.900 --> 00:07:23.490
is less than a times
the number of clauses,
00:07:23.490 --> 00:07:28.145
and OPT is at least b times
the number of clauses.
00:07:28.145 --> 00:07:32.240
00:07:32.240 --> 00:07:36.800
So whereas here everything
was relative to some input k
00:07:36.800 --> 00:07:40.080
that you want to
decide about, with SAT
00:07:40.080 --> 00:07:42.140
there's a kind of absolute
notion of what you'd
00:07:42.140 --> 00:07:44.450
like to achieve, which is
that you satisfy everything,
00:07:44.450 --> 00:07:45.770
all clauses are true.
00:07:45.770 --> 00:07:47.940
So typically we'll
think about b being one.
00:07:47.940 --> 00:07:50.780
00:07:50.780 --> 00:07:53.960
And so you're distinguishing
between a satisfiable instance
00:07:53.960 --> 00:07:56.630
where all clauses are
satisfied, and something
00:07:56.630 --> 00:07:58.000
that's very unsatisfiable.
00:07:58.000 --> 00:08:01.841
There's some kind of usually
constant fraction unsatisfiable
00:08:01.841 --> 00:08:02.340
clauses.
00:08:02.340 --> 00:08:05.750
00:08:05.750 --> 00:08:09.090
We need this level
of precision thinking
00:08:09.090 --> 00:08:11.909
about when you're right
up against 100% satisfied
00:08:11.909 --> 00:08:16.220
versus 1% satisfied or something
like that, or 1% satisfiable.
00:08:16.220 --> 00:08:19.409
00:08:19.409 --> 00:08:19.909
Cool.
00:08:19.909 --> 00:08:22.325
AUDIENCE: Do you use the same
notation for one here, or
00:08:22.325 --> 00:08:25.550
only for-- the Ones problem,
like the maximum number of ones
00:08:25.550 --> 00:08:26.050
you can get?
00:08:26.050 --> 00:08:28.800
PROFESSOR: I haven't
seen it, but yeah, that's
00:08:28.800 --> 00:08:30.200
a good question.
00:08:30.200 --> 00:08:32.790
Certainly valid to do
it for-- we will see it
00:08:32.790 --> 00:08:34.040
for one other type of problem.
00:08:34.040 --> 00:08:37.170
For any problem, if you can
define some absolute notion
00:08:37.170 --> 00:08:38.770
of how much you'd
like to get, you
00:08:38.770 --> 00:08:42.220
can always measure relative to
that and define this kind of a,
00:08:42.220 --> 00:08:45.190
b gap problem.
00:08:45.190 --> 00:08:47.160
Cool.
00:08:47.160 --> 00:08:47.660
All right.
00:08:47.660 --> 00:08:51.240
So how do we get these gaps?
00:08:51.240 --> 00:08:53.940
There's two, well maybe
three ways, I guess.
00:08:53.940 --> 00:09:01.370
00:09:01.370 --> 00:09:04.980
In general, we're going to
use reductions, like always.
00:09:04.980 --> 00:09:08.380
And you could start from
no gap and make a gap,
00:09:08.380 --> 00:09:10.430
or start from a
gap of additive one
00:09:10.430 --> 00:09:12.210
and turn it into a big
multiplicative gap.
00:09:12.210 --> 00:09:14.550
That will be
gap-producing reductions.
00:09:14.550 --> 00:09:17.390
You could start with some
gap and then make it bigger.
00:09:17.390 --> 00:09:19.940
That's gap-amplifying reduction.
00:09:19.940 --> 00:09:22.590
Or you could just start with
a gap and try to preserve it.
00:09:22.590 --> 00:09:24.510
That would be
gap-preserving reductions.
00:09:24.510 --> 00:09:26.450
In general, once
you have some gap,
00:09:26.450 --> 00:09:29.280
you try to keep it or make
it bigger to get stronger
00:09:29.280 --> 00:09:32.490
hardness for your problem.
00:09:32.490 --> 00:09:35.510
So the idea with a
gap-producing reduction
00:09:35.510 --> 00:09:38.700
is that you have no assumption
about your starting problem.
00:09:38.700 --> 00:09:40.825
In general, reduction we're
going from some problem
00:09:40.825 --> 00:09:42.930
A to some problem B.
00:09:42.930 --> 00:09:48.230
And what we would like is that
the output instance to problem
00:09:48.230 --> 00:09:57.750
B, the output of the
reduction has OPT equal to k
00:09:57.750 --> 00:10:06.000
or, for a minimization problem,
OPT bigger than c times k.
00:10:06.000 --> 00:10:09.920
And for a maximization problem,
OPT less than k over c.
00:10:09.920 --> 00:10:12.930
00:10:12.930 --> 00:10:15.380
So that's just saying we
have a gap in the output.
00:10:15.380 --> 00:10:17.840
We assume nothing about
the input instance.
00:10:17.840 --> 00:10:19.800
That would be a
gap-producing production.
00:10:19.800 --> 00:10:23.220
Now we have seen some of
these before, or at least
00:10:23.220 --> 00:10:24.300
mentioned them.
00:10:24.300 --> 00:10:26.430
One of them, this is
from lecture three,
00:10:26.430 --> 00:10:27.960
I think for Tetris.
00:10:27.960 --> 00:10:30.880
We proved NP hardness, which was
this three partition reduction.
00:10:30.880 --> 00:10:33.580
And the idea is that if you
could satisfy that and open
00:10:33.580 --> 00:10:37.130
this thing, then you could get
a zillion points down here.
00:10:37.130 --> 00:10:38.860
In most of the
instances down here,
00:10:38.860 --> 00:10:41.180
we squeeze this down to
like an n to the epsilon.
00:10:41.180 --> 00:10:42.820
That's still hard.
00:10:42.820 --> 00:10:46.010
And so n to the 1 minus epsilon
of the instances down here,
00:10:46.010 --> 00:10:49.830
and you're given a ton of
pieces to fill in the space,
00:10:49.830 --> 00:10:51.010
get lots of points.
00:10:51.010 --> 00:10:54.760
If the answer was no here, then
you won't get those points.
00:10:54.760 --> 00:10:59.410
And so OPT is very small, at
most, say, n to the epsilon.
00:10:59.410 --> 00:11:01.126
If you can solve
this instance, we
00:11:01.126 --> 00:11:06.100
have a yes instance in the
input, then we get n points.
00:11:06.100 --> 00:11:08.710
So the gap there is n
to the 1 minus epsilon.
00:11:08.710 --> 00:11:13.183
00:11:13.183 --> 00:11:16.880
So the Tetris reduction, we
assume nothing about the three
00:11:16.880 --> 00:11:17.680
partition instance.
00:11:17.680 --> 00:11:19.180
It was just yes or no.
00:11:19.180 --> 00:11:24.163
And we produced an instance
that had a gap of n
00:11:24.163 --> 00:11:25.330
to the 1 minus epsilon.
00:11:25.330 --> 00:11:27.340
We could set epsilon
to any constant
00:11:27.340 --> 00:11:30.660
we want bigger than zero.
00:11:30.660 --> 00:11:34.100
We also mentioned
another such reduction.
00:11:34.100 --> 00:11:36.340
And in general, for a
lot of games and puzzles,
00:11:36.340 --> 00:11:37.090
you can do this.
00:11:37.090 --> 00:11:38.850
It's sort of on all
or nothing deal.
00:11:38.850 --> 00:11:43.220
And gap-producing reduction
is a way to formalize that.
00:11:43.220 --> 00:11:46.260
Another problem we talked
about last class I believe
00:11:46.260 --> 00:11:48.770
was non-metric TSP.
00:11:48.770 --> 00:11:51.080
I just give you
a complete graph.
00:11:51.080 --> 00:11:54.250
Every edge has some number on it
that's the length of that edge.
00:11:54.250 --> 00:11:57.220
You want to find a TSP tour
of minimum total length.
00:11:57.220 --> 00:12:02.140
This is really hard to
approximate because depending
00:12:02.140 --> 00:12:08.210
on your model, you can use
let's say edge weights.
00:12:08.210 --> 00:12:12.830
And to be really annoying
would be 0, comma 1.
00:12:12.830 --> 00:12:16.100
And if I'm given a
Hamiltonicity instance, wherever
00:12:16.100 --> 00:12:18.180
there's an edge, I
put a weight of zero.
00:12:18.180 --> 00:12:20.750
Wherever there's not an
edge, I put a weight of one.
00:12:20.750 --> 00:12:23.310
And then if the input
graph was Hamiltonian,
00:12:23.310 --> 00:12:24.210
it's a yes instance.
00:12:24.210 --> 00:12:27.640
Then the output thing will
have a tour of length zero.
00:12:27.640 --> 00:12:31.750
And if the input
was not Hamiltonian,
00:12:31.750 --> 00:12:34.340
then the output
will have weight n.
00:12:34.340 --> 00:12:36.530
Ratio between n and
zero is infinity.
00:12:36.530 --> 00:12:39.080
So this is an
infinite gap creation
00:12:39.080 --> 00:12:40.890
if you allow weights of zero.
00:12:40.890 --> 00:12:43.340
If you say zero
is cheating, which
00:12:43.340 --> 00:12:46.890
we did and some papers
do, you could instead
00:12:46.890 --> 00:12:50.960
do one and infinity, where
infinity is the largest
00:12:50.960 --> 00:12:52.230
representable number.
00:12:52.230 --> 00:12:54.680
So that's going to be
something like 2 to the n
00:12:54.680 --> 00:12:59.480
if you allow usual binary
encodings of numbers.
00:12:59.480 --> 00:13:01.850
If you don't, the
PB case, then that
00:13:01.850 --> 00:13:03.910
would be n to some constant.
00:13:03.910 --> 00:13:06.530
But you get a big
gap in any case.
00:13:06.530 --> 00:13:12.680
So you get some gap equals huge.
00:13:12.680 --> 00:13:16.200
So these are kind of trivial
senses of inapproximability,
00:13:16.200 --> 00:13:18.540
but hey, that's
one way to do it.
00:13:18.540 --> 00:13:20.040
What we're going
to talk about today
00:13:20.040 --> 00:13:24.960
are other known ways to get
gap production that are really
00:13:24.960 --> 00:13:26.650
cool and more broadly useful.
00:13:26.650 --> 00:13:29.690
This is useful when you have a
sort of all or nothing problem.
00:13:29.690 --> 00:13:31.350
A lot of the time,
it's not so clear.
00:13:31.350 --> 00:13:33.560
There's a constant
factor approximation.
00:13:33.560 --> 00:13:36.819
So some giant gap like this
isn't going to be possible,
00:13:36.819 --> 00:13:37.985
but still gaps are possible.
00:13:37.985 --> 00:13:40.920
00:13:40.920 --> 00:13:49.690
Now, an important part of the
story here is the PCP theorem.
00:13:49.690 --> 00:13:52.550
So this is not about drugs.
00:13:52.550 --> 00:14:01.340
This is about another
complexity class.
00:14:01.340 --> 00:14:03.830
And the complexity
class is normally
00:14:03.830 --> 00:14:06.580
written PCP(log n, O(1)).
00:14:06.580 --> 00:14:09.970
I'm going to simplify this
to just PCP as the class.
00:14:09.970 --> 00:14:12.290
The other notions
make sense here,
00:14:12.290 --> 00:14:15.160
although the parameters don't
turn out to matter too much.
00:14:15.160 --> 00:14:17.750
And it's rather lengthy
to write that every time.
00:14:17.750 --> 00:14:20.300
So I'm just going to write PCP.
00:14:20.300 --> 00:14:23.830
Let me first tell you what
this class is about briefly,
00:14:23.830 --> 00:14:26.440
and then we'll see why
it's directly related
00:14:26.440 --> 00:14:29.460
to gap problems,
hence where a lot
00:14:29.460 --> 00:14:32.500
of these gap-producing
reductions come from.
00:14:32.500 --> 00:14:36.140
So PCP stands for
Probabilistically Checkable
00:14:36.140 --> 00:14:36.640
Proof.
00:14:36.640 --> 00:14:48.230
00:14:48.230 --> 00:14:53.390
The checkable
proof refers to NP.
00:14:53.390 --> 00:14:55.560
Every yes instance
has a checkable proof
00:14:55.560 --> 00:14:57.430
that the answer is yes.
00:14:57.430 --> 00:14:58.980
Probabilistically
checkable means
00:14:58.980 --> 00:15:02.150
you can check it even faster
with high probability.
00:15:02.150 --> 00:15:06.470
So normally to check a proof,
we take polynomial time in NP.
00:15:06.470 --> 00:15:09.860
Here we want to
achieve constant time.
00:15:09.860 --> 00:15:11.130
That's the main idea.
00:15:11.130 --> 00:15:13.720
That can't be done perfectly,
but you can do it correctly
00:15:13.720 --> 00:15:15.250
with high probability.
00:15:15.250 --> 00:15:18.220
So in general, a
problem in PCP has
00:15:18.220 --> 00:15:20.740
certificates of polynomial
length, just like NP.
00:15:20.740 --> 00:15:31.030
00:15:31.030 --> 00:15:37.560
And we have an algorithm for
checking certificates, which
00:15:37.560 --> 00:15:44.590
is given certificate,
and it's given order log
00:15:44.590 --> 00:15:46.785
n bits of randomness.
00:15:46.785 --> 00:15:53.740
00:15:53.740 --> 00:15:56.060
That's what this first
parameter refers to,
00:15:56.060 --> 00:15:58.475
is how much randomness
the algorithm's given.
00:15:58.475 --> 00:16:00.100
So we restrict the
amount of randomness
00:16:00.100 --> 00:16:03.180
to a very small amount.
00:16:03.180 --> 00:16:05.840
And it should tell you
whether the instance
00:16:05.840 --> 00:16:08.710
is a yes instance
or a no instance,
00:16:08.710 --> 00:16:11.350
in some sense if you're
given the right certificate.
00:16:11.350 --> 00:16:14.380
So in particular,
if the instance
00:16:14.380 --> 00:16:18.490
was a yes instance-- so this
is back to decision problems,
00:16:18.490 --> 00:16:19.110
just like NP.
00:16:19.110 --> 00:16:21.700
There's no optimization here.
00:16:21.700 --> 00:16:23.980
But we're going to apply
this to gap problems,
00:16:23.980 --> 00:16:27.410
and that will relate
us to optimization.
00:16:27.410 --> 00:16:39.210
So let's say there's no error
on yes instances, although you
00:16:39.210 --> 00:16:39.950
could relax that.
00:16:39.950 --> 00:16:42.119
It won't make a big difference.
00:16:42.119 --> 00:16:46.000
So if you have a yes instance,
and you give the right
00:16:46.000 --> 00:16:54.599
certificate-- so this is
for some certificate--
00:16:54.599 --> 00:16:56.210
the algorithm's
guaranteed to say yes.
00:16:56.210 --> 00:16:57.950
So no error there.
00:16:57.950 --> 00:17:03.010
Where we add some slack is
if there's a no instance.
00:17:03.010 --> 00:17:05.560
Now normally in NP
for a no instance,
00:17:05.560 --> 00:17:08.820
there is no correct certificate.
00:17:08.820 --> 00:17:10.520
Now, the algorithm
will sometimes
00:17:10.520 --> 00:17:13.590
say yes even if we give
it the wrong certificate.
00:17:13.590 --> 00:17:15.230
There is no right certificate.
00:17:15.230 --> 00:17:19.772
But it will say so with some
at most constant probability.
00:17:19.772 --> 00:17:26.640
So let's say the probability
that the algorithm says
00:17:26.640 --> 00:17:36.360
no is at least some constant,
presumably less than one.
00:17:36.360 --> 00:17:38.730
If it's one, then that's NP.
00:17:38.730 --> 00:17:41.740
If it's a half,
that would be fine.
00:17:41.740 --> 00:17:44.770
A tenth, a hundredth,
they'll all be the same.
00:17:44.770 --> 00:17:46.710
Because once you have
such an algorithm that
00:17:46.710 --> 00:17:48.440
achieves some
constant probability,
00:17:48.440 --> 00:17:52.835
you could apply it log
1 over epsilon times.
00:17:52.835 --> 00:17:55.880
00:17:55.880 --> 00:18:01.720
And we reduce the
error to epsilon.
00:18:01.720 --> 00:18:04.694
00:18:04.694 --> 00:18:07.110
The probability of error goes
to epsilon if we just repeat
00:18:07.110 --> 00:18:08.810
this log 1 over epsilon times.
00:18:08.810 --> 00:18:13.440
So in constant
time-- it didn't say.
00:18:13.440 --> 00:18:16.880
The order one here refers to the
running time of the algorithm.
00:18:16.880 --> 00:18:23.540
So this is an order
one time algorithm.
00:18:23.540 --> 00:18:25.620
So the point is, the
algorithm's super fast
00:18:25.620 --> 00:18:28.520
and still in constant
time for constant epsilon.
00:18:28.520 --> 00:18:31.630
You can get arbitrarily
small error probability,
00:18:31.630 --> 00:18:34.200
say one in 100 or
one in a million,
00:18:34.200 --> 00:18:37.140
and it's still pretty good.
00:18:37.140 --> 00:18:40.190
And you're checking your
proof super, super fast.
00:18:40.190 --> 00:18:41.128
Question.
00:18:41.128 --> 00:18:43.470
AUDIENCE: Why is there a
limit on the randomness?
00:18:43.470 --> 00:18:45.852
00:18:45.852 --> 00:18:47.310
PROFESSOR: This
limit on randomness
00:18:47.310 --> 00:18:49.816
is not strictly necessary.
00:18:49.816 --> 00:18:51.190
For example, n
bits of randomness
00:18:51.190 --> 00:18:52.314
turned out not to help you.
00:18:52.314 --> 00:18:53.560
That was proved later.
00:18:53.560 --> 00:18:56.050
But we're going to
use this in a moment.
00:18:56.050 --> 00:18:59.360
It will help us simulate this
algorithm without randomness,
00:18:59.360 --> 00:19:00.409
basically.
00:19:00.409 --> 00:19:01.347
Yeah.
00:19:01.347 --> 00:19:03.692
AUDIENCE: If the verifier
runs in constant time,
00:19:03.692 --> 00:19:06.040
can it either read
or was written?
00:19:06.040 --> 00:19:10.550
PROFESSOR: So this is constant
time in a model of computation
00:19:10.550 --> 00:19:12.880
where you can read log
n bits in one step.
00:19:12.880 --> 00:19:15.082
So your word, let's
say, is log n bits long.
00:19:15.082 --> 00:19:17.040
So you have enough time
to read the randomness.
00:19:17.040 --> 00:19:19.289
Obviously you don't have
time to read the certificate,
00:19:19.289 --> 00:19:21.020
because that has
polynomial length.
00:19:21.020 --> 00:19:24.550
But yeah, constant time.
00:19:24.550 --> 00:19:25.420
Cool.
00:19:25.420 --> 00:19:26.330
Other questions?
00:19:26.330 --> 00:19:28.960
So that is the
definition of PCP.
00:19:28.960 --> 00:19:33.755
Now let me relate
it to gap problems.
00:19:33.755 --> 00:19:36.510
00:19:36.510 --> 00:19:58.180
So let's say first claim is
that if we look at this gap SAT
00:19:58.180 --> 00:20:02.340
problem, where b equals one and
a is some constant, presumably
00:20:02.340 --> 00:20:07.810
less than one, then-- in fact,
that should be less than one.
00:20:07.810 --> 00:20:13.260
Why did I write strictly
less than 1 here?
00:20:13.260 --> 00:20:15.120
This is a constant
less than one.
00:20:15.120 --> 00:20:21.249
Then I claim that
problem is in PCP,
00:20:21.249 --> 00:20:23.040
that there is a
probabilistically checkable
00:20:23.040 --> 00:20:24.460
proof for this instance.
00:20:24.460 --> 00:20:27.590
Namely, it's a satisfying
variable assignment.
00:20:27.590 --> 00:20:30.000
Again, this instance
either has the prop--
00:20:30.000 --> 00:20:32.670
when in a yes instance
all of the entire thing
00:20:32.670 --> 00:20:33.720
is satisfiable.
00:20:33.720 --> 00:20:41.980
So just like before, I
can have a certificate,
00:20:41.980 --> 00:20:46.791
just like an NP satisfying
assignment to the variables
00:20:46.791 --> 00:20:47.290
is good.
00:20:47.290 --> 00:20:51.730
00:20:51.730 --> 00:20:54.780
In the no instance, now I
know, let's say, at most half
00:20:54.780 --> 00:20:58.840
of the things are satisfied
if this is one half.
00:20:58.840 --> 00:21:01.960
And so what is my
algorithm going to do?
00:21:01.960 --> 00:21:04.800
00:21:04.800 --> 00:21:07.830
In order to get some at
most constant probability
00:21:07.830 --> 00:21:10.962
of failure, it's going
to choose a random clause
00:21:10.962 --> 00:21:12.295
and check that it was satisfied.
00:21:12.295 --> 00:21:31.030
00:21:31.030 --> 00:21:32.300
Uniform random.
00:21:32.300 --> 00:21:34.080
So I've got log n bits.
00:21:34.080 --> 00:21:36.000
Let's say there are n clauses.
00:21:36.000 --> 00:21:41.230
So I can choose one of them at
random by flipping log n coins.
00:21:41.230 --> 00:21:46.415
And then check so that
involves-- this is 3SAT.
00:21:46.415 --> 00:21:48.070
It only involves
three variables.
00:21:48.070 --> 00:21:50.680
I check those three
variable value assignments
00:21:50.680 --> 00:21:54.880
in my certificate by random
access into the certificate.
00:21:54.880 --> 00:21:57.195
In constant time, I
determine whether that clause
00:21:57.195 --> 00:21:58.140
is satisfied.
00:21:58.140 --> 00:22:00.790
If the clause is satisfied,
algorithm returns yes.
00:22:00.790 --> 00:22:02.280
Otherwise, return no.
00:22:02.280 --> 00:22:04.250
Now, if it was a
satisfying assignment,
00:22:04.250 --> 00:22:06.250
the algorithm will
always say yes.
00:22:06.250 --> 00:22:07.830
So that's good.
00:22:07.830 --> 00:22:10.510
If it was not
satisfiable, we know
00:22:10.510 --> 00:22:14.200
that, let's say at most half
of the clauses are satisfiable.
00:22:14.200 --> 00:22:16.520
Which means in
every certificate,
00:22:16.520 --> 00:22:19.710
the algorithm will say no
at least half the time.
00:22:19.710 --> 00:22:22.910
And half is whatever
that constant is.
00:22:22.910 --> 00:22:28.090
So that means the probability
that the algorithm
00:22:28.090 --> 00:22:38.690
is wrong is less than 1 over
the gap, whatever that ratio is.
00:22:38.690 --> 00:22:40.210
Cool?
00:22:40.210 --> 00:22:40.760
Yeah.
00:22:40.760 --> 00:22:42.520
AUDIENCE: So
does this proof
00:22:42.520 --> 00:22:45.260
not then hold for
general CNF?
00:22:45.260 --> 00:22:46.310
So for O(1)-CNF?
00:22:46.310 --> 00:22:49.130
00:22:49.130 --> 00:22:55.180
PROFESSOR: Let me tell
you, the PCP theorem
00:22:55.180 --> 00:22:59.220
is that NP equals PCP.
00:22:59.220 --> 00:23:00.040
This is proved.
00:23:00.040 --> 00:23:02.600
So all problems are in PCP.
00:23:02.600 --> 00:23:05.870
But this is some motivation
for where this class came from.
00:23:05.870 --> 00:23:09.710
00:23:09.710 --> 00:23:11.260
I'm not going to
prove this theorem.
00:23:11.260 --> 00:23:12.740
The original proof
is super long.
00:23:12.740 --> 00:23:14.920
Since then, there have been
relatively short proofs.
00:23:14.920 --> 00:23:17.400
I think the shortest proof
currently is two pages long.
00:23:17.400 --> 00:23:19.390
Still not going to
prove it because it's
00:23:19.390 --> 00:23:24.230
a bit beside the
point to some extent.
00:23:24.230 --> 00:23:27.900
It does use reductions
and gap amplification,
00:23:27.900 --> 00:23:32.450
but it's technical to
prove it, let's say.
00:23:32.450 --> 00:23:36.270
But I will give you some more
motivation for why it's true.
00:23:36.270 --> 00:23:47.380
So for example, so
here's one claim.
00:23:47.380 --> 00:23:53.320
If one-- let's
change this notation.
00:23:53.320 --> 00:24:07.670
If (<1, 1)-gap 3SAT
is NP-hard,
00:24:07.670 --> 00:24:13.150
then NP equals PCP.
00:24:13.150 --> 00:24:15.380
So we know that this
is true, but before we
00:24:15.380 --> 00:24:21.670
know that here-- so we just
proved that this thing is in PCP.
00:24:21.670 --> 00:24:25.349
And if furthermore
this problem--
00:24:25.349 --> 00:24:26.890
we're going to prove
this is NP-hard.
00:24:26.890 --> 00:24:29.360
That's the motivation.
00:24:29.360 --> 00:24:31.300
If you believe
that it's NP-hard,
00:24:31.300 --> 00:24:34.830
then we know all problems in
NP can reduce to this thing.
00:24:34.830 --> 00:24:36.480
And then that thing is in PCP.
00:24:36.480 --> 00:24:38.850
So that tells us that
all problems in NP,
00:24:38.850 --> 00:24:42.590
you can convert them into
(<1, 1)-gap 3SAT
00:24:42.590 --> 00:24:46.030
and then get a PCP
algorithm for them.
00:24:46.030 --> 00:24:49.690
So that would be one way
to prove the PCP theorem.
00:24:49.690 --> 00:24:52.990
In fact, the reverse
is also true.
00:24:52.990 --> 00:24:57.270
And this is sort of more
directly useful to us.
00:24:57.270 --> 00:25:17.680
If, let's say, 3SAT is in PCP,
then the gap version of 3SAT
00:25:17.680 --> 00:25:18.180
is NP-hard.
00:25:18.180 --> 00:25:21.600
00:25:21.600 --> 00:25:26.130
This is interesting
because-- this is true
00:25:26.130 --> 00:25:30.790
because NP equals PCP, in
particular 3SAT is in PCP.
00:25:30.790 --> 00:25:32.680
And so we're going to
be able to conclude,
00:25:32.680 --> 00:25:36.350
by a very short argument,
that the gap version of 3SAT
00:25:36.350 --> 00:25:37.240
is also NP-hard.
00:25:37.240 --> 00:25:40.220
And this proves constant factor
inapproximability of 3SAT.
00:25:40.220 --> 00:25:42.290
We will see a tighter
constant in a little bit,
00:25:42.290 --> 00:25:46.340
but this will be our
first such bound.
00:25:46.340 --> 00:25:48.365
And this is a very
general kind of algorithm.
00:25:48.365 --> 00:25:49.300
It's kind of cool.
00:25:49.300 --> 00:25:52.590
00:25:52.590 --> 00:25:55.810
So PCP is easy for the
gap version of 3SAT.
00:25:55.810 --> 00:25:58.470
But suppose there was a
probabilistically checkable
00:25:58.470 --> 00:26:01.410
proof for just straight up
3SAT when you're not given
00:26:01.410 --> 00:26:04.550
any gap bound, which is true.
00:26:04.550 --> 00:26:07.080
It does exist.
00:26:07.080 --> 00:26:09.080
So we're going to
use that algorithm.
00:26:09.080 --> 00:26:12.240
And we're going to do a
gap-preserving reduction.
00:26:12.240 --> 00:26:22.780
00:26:22.780 --> 00:26:25.410
The PCP algorithm we're given,
because we're looking at PCP(log n, O(1))
00:26:25.410 --> 00:26:29.300
runs in constant time.
00:26:29.300 --> 00:26:32.220
Constant time algorithm
can't do very much.
00:26:32.220 --> 00:26:34.700
In particular, I can
write the algorithm
00:26:34.700 --> 00:26:37.045
as a constant size formula.
00:26:37.045 --> 00:26:41.010
00:26:41.010 --> 00:26:43.740
It's really a distribution
over such formulas defined
00:26:43.740 --> 00:26:46.250
by the log n and the bits.
00:26:46.250 --> 00:26:49.740
But let's say it's a
random variable where
00:26:49.740 --> 00:26:53.700
for each possible random choice
is a constant size formula that
00:26:53.700 --> 00:26:56.010
evaluates to true or
false, corresponding
00:26:56.010 --> 00:26:57.770
to whether the algorithm
says yes or no.
00:26:57.770 --> 00:26:59.145
We know we can
convert algorithms
00:26:59.145 --> 00:27:03.850
to formulas if they're
a short amount of time.
00:27:03.850 --> 00:27:05.870
So we can make
that a CNF formula.
00:27:05.870 --> 00:27:08.370
Why not?
00:27:08.370 --> 00:27:10.010
3CNF if we want.
00:27:10.010 --> 00:27:14.350
My goal is to-- I
want to reduce 3SAT
00:27:14.350 --> 00:27:15.640
to the gap version of 3SAT.
00:27:15.640 --> 00:27:17.230
Because 3SAT we know is NP-hard.
00:27:17.230 --> 00:27:20.790
So if I can reduce it to the
gap version of 3SAT, I'm happy.
00:27:20.790 --> 00:27:23.860
Then I know the gap version
of 3SAT is also hard.
00:27:23.860 --> 00:27:25.235
So here is my reduction.
00:27:25.235 --> 00:27:29.760
00:27:29.760 --> 00:27:33.760
So I'm given the 3SAT
formula, and the algorithm
00:27:33.760 --> 00:27:37.760
evaluates some formula on
it and the certificate.
00:27:37.760 --> 00:27:49.414
What I'm going to do is try
all of the random choices.
00:27:49.414 --> 00:27:51.080
Because there's only
log n bits, there's
00:27:51.080 --> 00:27:54.120
only polynomially many possible
choices for those bits.
00:27:54.120 --> 00:27:57.470
00:27:57.470 --> 00:28:00.092
Order log n so it's
n to some constant.
00:28:00.092 --> 00:28:02.300
And I want to take this
formula, take the conjunction
00:28:02.300 --> 00:28:04.250
over all of those choices.
00:28:04.250 --> 00:28:07.590
If the algorithm
always says yes,
00:28:07.590 --> 00:28:10.240
then this formula
will be satisfied.
00:28:10.240 --> 00:28:14.680
So in the yes instance case,
I get a satisfiable formula.
00:28:14.680 --> 00:28:22.180
So yes, implies satisfiable,
100% satisfiable.
00:28:22.180 --> 00:28:24.910
That corresponds to this number.
00:28:24.910 --> 00:28:28.220
I want it to be 100%
in the yes case.
00:28:28.220 --> 00:28:36.150
In the no case, I know
that a constant fraction
00:28:36.150 --> 00:28:39.650
of these random
choices give a no.
00:28:39.650 --> 00:28:42.920
Meaning, they will
not be satisfied.
00:28:42.920 --> 00:28:47.160
For any choice,
any certificate, I
00:28:47.160 --> 00:28:51.340
know that a constant
fraction of these terms which
00:28:51.340 --> 00:28:55.600
I'm conjuncting will
evaluate to false because
00:28:55.600 --> 00:28:56.760
of the definition of PCP.
00:28:56.760 --> 00:29:01.810
That's what probability
algorithm saying no means.
00:29:01.810 --> 00:29:14.060
So it's a constant fraction
of the terms are false.
00:29:14.060 --> 00:29:16.750
00:29:16.750 --> 00:29:19.810
The terms are the things
we're conjuncting over.
00:29:19.810 --> 00:29:25.570
But each term here is a
constant size CNF formula.
00:29:25.570 --> 00:29:28.220
So when I AND those together,
I really just get one giant
00:29:28.220 --> 00:29:30.240
AND of clauses.
00:29:30.240 --> 00:29:32.830
Constant fraction larger
than the number of terms.
00:29:32.830 --> 00:29:35.910
And if a term is false,
that means at least one
00:29:35.910 --> 00:29:37.872
of the clauses is false.
00:29:37.872 --> 00:29:40.330
And there's only a constant
number of clauses in each term.
00:29:40.330 --> 00:29:42.910
So this means a
constant fraction
00:29:42.910 --> 00:29:47.010
of the clauses in that giant
conjunction are also false.
00:29:47.010 --> 00:29:56.000
00:29:56.000 --> 00:29:58.480
And that is essentially it.
00:29:58.480 --> 00:30:05.920
00:30:05.920 --> 00:30:07.000
That is my reduction.
00:30:07.000 --> 00:30:18.810
00:30:18.810 --> 00:30:22.040
So in the yes instance, I get
100% percent satisfiable thing.
00:30:22.040 --> 00:30:24.490
In the no instance,
I get some constant
00:30:24.490 --> 00:30:26.420
strictly less than
1 satisfiable thing.
00:30:26.420 --> 00:30:29.510
Because in any solution,
I get a constant fraction
00:30:29.510 --> 00:30:31.344
that turn out to be
false, constant fraction
00:30:31.344 --> 00:30:31.968
of the clauses.
00:30:31.968 --> 00:30:34.320
Now what the constant is,
you'd have to work out things.
00:30:34.320 --> 00:30:36.670
You'd have to know how
big your PCP algorithm is.
00:30:36.670 --> 00:30:40.460
But at least we get a
constant lower bound proving--
00:30:40.460 --> 00:30:45.030
in particular, proving there's
no PTAS for Max 3SAT.
00:30:45.030 --> 00:30:49.220
This is what you might call
a gap-amplifying reduction,
00:30:49.220 --> 00:30:51.650
in the sense we
started with no gap.
00:30:51.650 --> 00:30:54.440
The instance of 3SAT was
either true or false.
00:30:54.440 --> 00:30:57.605
And we ended up with something
with a significant gap.
00:30:57.605 --> 00:31:01.477
00:31:01.477 --> 00:31:03.060
So what we're going
to talk about next
00:31:03.060 --> 00:31:04.855
is called gap-preserving
reductions.
00:31:04.855 --> 00:31:10.360
00:31:10.360 --> 00:31:14.620
Maybe before I get there,
what we just showed
00:31:14.620 --> 00:31:18.870
is that the PCP
theorem is equivalent.
00:31:18.870 --> 00:31:22.100
And in particular, we get
gap problems being NP-hard.
00:31:22.100 --> 00:31:25.210
This is why we care about PCPs.
00:31:25.210 --> 00:31:29.680
And then in general,
once we have
00:31:29.680 --> 00:31:32.250
these kinds of gap
hardness results,
00:31:32.250 --> 00:31:35.170
we convert our-- when we're
thinking about reductions
00:31:35.170 --> 00:31:40.280
from A to B, because we know
gap implies inapproximability,
00:31:40.280 --> 00:31:43.100
we could say, OK, 3SAT
is inapproximable,
00:31:43.100 --> 00:31:46.890
and then do, say, an L reduction
from 3SAT to something else.
00:31:46.890 --> 00:31:50.000
The something else is
therefore inapproximable also.
00:31:50.000 --> 00:31:52.380
That's all good.
00:31:52.380 --> 00:31:54.100
But we can also,
instead of thinking
00:31:54.100 --> 00:31:57.590
about the inapproximability and
how much carries from A to B,
00:31:57.590 --> 00:32:00.050
we can think about
the gap directly.
00:32:00.050 --> 00:32:02.980
And this is sort of the main
approach in this lecture
00:32:02.980 --> 00:32:05.080
that I'm trying to
demonstrate is by preserving
00:32:05.080 --> 00:32:07.940
the gap directly,
a, well you get
00:32:07.940 --> 00:32:10.850
new gap bounds and generally
stronger gap bounds.
00:32:10.850 --> 00:32:13.810
And then those imply
inapproximability results.
00:32:13.810 --> 00:32:16.600
But the gap bounds are stronger
than the inapproximability,
00:32:16.600 --> 00:32:19.630
and also they tend to give
larger constant factors
00:32:19.630 --> 00:32:22.530
in the inapproximability
results.
00:32:22.530 --> 00:32:27.130
So what do we want out of
a gap-preserving reduction?
00:32:27.130 --> 00:32:35.220
Let's say we have
an instance x of A.
00:32:35.220 --> 00:32:44.440
We convert that into an instance
x' of some problem B.
00:32:44.440 --> 00:32:46.430
We're just going to
think about the OPT of x
00:32:46.430 --> 00:32:49.300
versus the OPT of x'.
00:32:49.300 --> 00:32:54.480
And what we want for, let's
say, a minimization problem
00:32:54.480 --> 00:32:57.830
is two properties.
00:32:57.830 --> 00:33:04.270
One is that the OPT-- if the
OPT of x is at most some k,
00:33:04.270 --> 00:33:11.770
then the OPT of x'
is at most some k'.
00:33:11.770 --> 00:33:14.120
And conversely.
00:33:14.120 --> 00:33:30.820
00:33:30.820 --> 00:33:32.790
So in general, OPT
may not be preserved.
00:33:32.790 --> 00:33:37.410
But let's say it changes
by some prime operation.
00:33:37.410 --> 00:33:45.469
So in fact, you can think of k
and k prime as functions of n.
00:33:45.469 --> 00:33:49.159
So if I know that OPT of x is
at most some function of n,
00:33:49.159 --> 00:33:52.611
then I get that OPT of x'
is at most some other function
00:33:52.611 --> 00:33:53.560
of n.
00:33:53.560 --> 00:33:55.920
But there's some known
relation between the two.
00:33:55.920 --> 00:33:58.260
What I care about is this gap c.
00:33:58.260 --> 00:34:00.360
Should be a c' here.
00:34:00.360 --> 00:34:03.810
So what this is saying is
suppose I had a gap, if I know
00:34:03.810 --> 00:34:06.600
that all the solutions
are either less than k
00:34:06.600 --> 00:34:09.530
or more than c times
k, I want that to be
00:34:09.530 --> 00:34:11.790
preserved for some
possibly other gap c'
00:34:11.790 --> 00:34:13.687
in the new problem.
00:34:13.687 --> 00:34:16.020
So this is pretty general,
but this is the sort of thing
00:34:16.020 --> 00:34:17.440
we want to preserve.
00:34:17.440 --> 00:34:21.179
If we had a gap of c before,
we get some gap c' after.
00:34:21.179 --> 00:34:25.100
If c' equals c, this would
be a perfectly gap-preserving
00:34:25.100 --> 00:34:25.600
reduction.
00:34:25.600 --> 00:34:27.940
Maybe we'll lose
some constant factor.
00:34:27.940 --> 00:34:30.980
If c' is
greater than c, this
00:34:30.980 --> 00:34:32.780
is called gap amplification.
00:34:32.780 --> 00:34:38.650
00:34:38.650 --> 00:34:41.220
And gap amplification
is essentially
00:34:41.220 --> 00:34:48.290
how the PCP theorem is
shown, by repeatedly
00:34:48.290 --> 00:34:51.170
growing the gap until
it's something reasonable.
00:34:51.170 --> 00:34:54.900
And if you want to, say, prove
that set cover is log n hard,
00:34:54.900 --> 00:34:57.190
it's a similar thing where
you start with a small gap
00:34:57.190 --> 00:34:59.110
constant factor, and
then you grow it,
00:34:59.110 --> 00:35:01.920
and you show you can grow it
to log n before you run out
00:35:01.920 --> 00:35:04.510
of space to write it in
your problem essentially,
00:35:04.510 --> 00:35:07.380
before your instance gets
more than polynomial.
00:35:07.380 --> 00:35:09.740
Or if you want to prove that
Clique can't be solved
00:35:09.740 --> 00:35:13.670
in better than whatever
n to the 1 minus epsilon,
00:35:13.670 --> 00:35:17.010
then a similar trick of
gap amplification works.
00:35:17.010 --> 00:35:19.580
Those amplification
arguments are involved,
00:35:19.580 --> 00:35:22.760
and so I'm not going
to show them here.
00:35:22.760 --> 00:35:25.760
But I will show you an example
of a gap-preserving reduction
00:35:25.760 --> 00:35:27.185
next, unless there
are questions.
00:35:27.185 --> 00:35:30.430
00:35:30.430 --> 00:35:38.690
Cool. So I'm going to
reduce a problem which
00:35:38.690 --> 00:35:52.720
we have mentioned
before, which is Max
00:35:52.720 --> 00:35:55.820
exactly-3 XOR-and-XNOR SAT.
00:35:55.820 --> 00:35:59.260
This is linear equations
modulo two,
00:35:59.260 --> 00:36:04.710
where every equation
has exactly three terms.
00:36:04.710 --> 00:36:15.086
So something like x_i XOR x_j
XOR x_k equals 1, or something.
00:36:15.086 --> 00:36:16.460
You can also have
negations here.
00:36:16.460 --> 00:36:19.030
00:36:19.030 --> 00:36:22.960
So I have a bunch of
equations like that.
00:36:22.960 --> 00:36:25.691
I'm going to just tell you
a gap bound on this problem,
00:36:25.691 --> 00:36:28.190
and then we're going to reduce
it to another problem, namely
00:36:28.190 --> 00:36:30.790
Max E3SAT.
00:36:30.790 --> 00:36:34.860
So the claim here
is that this problem
00:36:34.860 --> 00:36:41.150
is one half plus epsilon,
one minus epsilon, gap
00:36:41.150 --> 00:36:45.560
hard for any epsilon.
00:36:45.560 --> 00:36:50.960
00:36:50.960 --> 00:36:52.420
Which in particular
implies that it
00:36:52.420 --> 00:36:56.330
is one half minus
epsilon inapproximable,
00:36:56.330 --> 00:36:57.520
unless P equals NP.
00:36:57.520 --> 00:37:00.899
00:37:00.899 --> 00:37:02.190
But this is of course stronger.
00:37:02.190 --> 00:37:05.390
It says if you just
look at instances where
00:37:05.390 --> 00:37:14.020
let's say 99% of the equations
are satisfiable versus when
00:37:14.020 --> 00:37:18.560
51% are satisfiable, it's
NP-hard to distinguish
00:37:18.560 --> 00:37:19.310
between those two.
00:37:19.310 --> 00:37:22.570
00:37:22.570 --> 00:37:24.440
Why one half here?
00:37:24.440 --> 00:37:26.355
Because there is a one
half approximation.
00:37:26.355 --> 00:37:31.330
00:37:31.330 --> 00:37:33.230
I've kind of mentioned
the general approach
00:37:33.230 --> 00:37:35.273
for approximation
algorithms for SAT
00:37:35.273 --> 00:37:39.480
is take a random assignment,
variable assignment.
00:37:39.480 --> 00:37:45.110
And in this case, because these
statements are about a parity,
00:37:45.110 --> 00:37:46.830
if you think of x_k
as random, it doesn't
00:37:46.830 --> 00:37:48.450
matter what these two are.
00:37:48.450 --> 00:37:50.670
50% probability this
will be satisfied.
00:37:50.670 --> 00:37:54.080
And so you can always satisfy
at least half of the clauses
00:37:54.080 --> 00:37:57.200
because this randomized
algorithm will satisfy half
00:37:57.200 --> 00:37:58.040
in expectation.
00:37:58.040 --> 00:38:01.340
Therefore, in at least one
instance, it will do so.
00:38:01.340 --> 00:38:03.240
But if you allow
randomized approximation,
00:38:03.240 --> 00:38:06.300
this is a one half approximation
or a two approximation,
00:38:06.300 --> 00:38:09.020
depending on your perspective.
00:38:09.020 --> 00:38:11.200
So this is really tight.
00:38:11.200 --> 00:38:12.370
That's good news.
00:38:12.370 --> 00:38:18.080
And this is essentially a
form of the PCP theorem.
00:38:18.080 --> 00:38:23.570
PCP theorem says that
there's some algorithm,
00:38:23.570 --> 00:38:26.470
and you can prove that in fact
there is an algorithm that
00:38:26.470 --> 00:38:27.300
looks like this.
00:38:27.300 --> 00:38:34.510
It's a bunch of linear equations
with three terms per equation.
00:38:34.510 --> 00:38:38.800
So let's take that as given.
00:38:38.800 --> 00:38:44.190
00:38:44.190 --> 00:38:47.450
Now, what I want to
show is a reduction
00:38:47.450 --> 00:38:51.940
from that problem to Max E3SAT.
00:38:51.940 --> 00:39:01.340
So remember Max E3SAT,
you're given
00:39:01.340 --> 00:39:04.180
CNF where every
clause has exactly
00:39:04.180 --> 00:39:07.340
three distinct literals.
00:39:07.340 --> 00:39:10.600
You want to maximize the
number of satisfied things.
00:39:10.600 --> 00:39:14.170
So this is roughly the problem
we were talking about up there.
00:39:14.170 --> 00:39:16.730
00:39:16.730 --> 00:39:25.070
So first thing
I'm going to do is
00:39:25.070 --> 00:39:29.340
I want to reduce this to that.
00:39:29.340 --> 00:39:32.200
And this is the reduction.
00:39:32.200 --> 00:39:34.470
And the first claim is just
that it's an L-reduction.
00:39:34.470 --> 00:39:36.180
So that's something
we're familiar with.
00:39:36.180 --> 00:39:37.430
Let's think about it that way.
00:39:37.430 --> 00:39:41.010
Then we will think about it
in a gap-preserving sense.
00:39:41.010 --> 00:39:45.000
So there are two types of
equations we need to satisfy,
00:39:45.000 --> 00:39:49.047
the sort of odd case
or the even case.
00:39:49.047 --> 00:39:50.630
Again, each of these
could be negated.
00:39:50.630 --> 00:39:54.420
I'm just going to double negate
means unnegated over here.
00:39:54.420 --> 00:39:58.050
So each equation is going to
be replaced with exactly four
00:39:58.050 --> 00:40:02.760
clauses in the E3SAT instance.
00:40:02.760 --> 00:40:11.160
And the idea is, well, if I want
the parity of them to be odd,
00:40:11.160 --> 00:40:13.900
it should be the case that
at least one of them is true.
00:40:13.900 --> 00:40:17.180
And if you stare at it
long enough, also when
00:40:17.180 --> 00:40:21.390
you put two bars in there, I
don't want exactly two of them
00:40:21.390 --> 00:40:22.040
to be true.
00:40:22.040 --> 00:40:23.470
That's the parity constraint.
00:40:23.470 --> 00:40:28.300
If this is true, all four
of these should be true.
00:40:28.300 --> 00:40:30.640
That's the first claim,
just by the parity
00:40:30.640 --> 00:40:32.190
of the number of bars.
00:40:32.190 --> 00:40:35.510
There's either zero
bars or two bars,
00:40:35.510 --> 00:40:39.210
or three positive
or one positive.
00:40:39.210 --> 00:40:40.890
That's the two cases.
00:40:40.890 --> 00:40:47.100
And in this situation where
I want the parity to be even,
00:40:47.100 --> 00:40:51.290
even number of trues, I
have all the even number
00:40:51.290 --> 00:40:53.690
of trues cases over here.
00:40:53.690 --> 00:40:57.236
Here are two of them even,
and here none of them even.
00:40:57.236 --> 00:41:00.200
00:41:00.200 --> 00:41:03.110
And again, if this is satisfied,
then all four of those
00:41:03.110 --> 00:41:04.750
are satisfied.
00:41:04.750 --> 00:41:09.800
Now, if these are not
satisfied, by the same argument
00:41:09.800 --> 00:41:12.150
you can show that at least
one of these is violated.
00:41:12.150 --> 00:41:15.440
But in fact, just
one will be violated.
00:41:15.440 --> 00:41:19.860
So for example, so this
is just a case analysis.
00:41:19.860 --> 00:41:23.000
Let's say I set all
of these to be zero,
00:41:23.000 --> 00:41:25.950
and so their XOR is
zero and not one.
00:41:25.950 --> 00:41:29.770
So if they're all false, then
this will not be satisfied,
00:41:29.770 --> 00:41:33.150
but the other three will be.
00:41:33.150 --> 00:41:36.200
And in general, because
we have, for example,
00:41:36.200 --> 00:41:39.820
x_i appearing true and
false in different cases,
00:41:39.820 --> 00:41:44.190
you will satisfy
three out of four
00:41:44.190 --> 00:41:47.230
on the right when you
don't satisfy on the left.
00:41:47.230 --> 00:41:49.787
So the difference is
three versus four.
00:41:49.787 --> 00:41:52.120
When these are satisfied, you
satisfy four on the right.
00:41:52.120 --> 00:41:54.495
When they're unsatisfied, you
satisfy three on the right.
00:41:54.495 --> 00:41:55.410
That's all.
00:41:55.410 --> 00:41:55.910
Claiming.
00:41:55.910 --> 00:42:03.760
00:42:03.760 --> 00:42:09.040
So if the equation
is satisfied, then we
00:42:09.040 --> 00:42:15.420
get four in the 3SAT instance.
00:42:15.420 --> 00:42:23.170
And if it's unsatisfied, we
turn out to get exactly three.
00:42:23.170 --> 00:42:29.780
00:42:29.780 --> 00:42:32.680
So I want to prove that
this is an L-reduction.
00:42:32.680 --> 00:42:34.440
To prove L-reduction,
we need two things.
00:42:34.440 --> 00:42:39.380
One is that the additive gap,
if I solve the 3SAT instance
00:42:39.380 --> 00:42:44.070
and convert it back into
a corresponding solution
00:42:44.070 --> 00:42:48.230
to Max E3-XNOR-SAT, which
don't change anything.
00:42:48.230 --> 00:42:50.880
The variables are just
what they were before.
00:42:50.880 --> 00:42:54.470
That the additive gap
from OPT on the right side
00:42:54.470 --> 00:42:57.670
is at most some constant
times the additive gap
00:42:57.670 --> 00:43:00.460
on the left side, or vice versa.
00:43:00.460 --> 00:43:03.340
In this case, the gap is
exactly preserved because it's
00:43:03.340 --> 00:43:04.800
four versus three over here.
00:43:04.800 --> 00:43:06.480
It's one versus zero over here.
00:43:06.480 --> 00:43:09.250
So additive gap remains one.
00:43:09.250 --> 00:43:15.665
And that is called beta, I
think, in L-reduction land.
00:43:15.665 --> 00:43:21.720
00:43:21.720 --> 00:43:25.080
So this was property
two in the L-reduction.
00:43:25.080 --> 00:43:34.630
So the additive error in this
case is exactly preserved.
00:43:34.630 --> 00:43:38.130
00:43:38.130 --> 00:43:39.080
So there's no scale.
00:43:39.080 --> 00:43:42.030
Beta equals one.
00:43:42.030 --> 00:43:45.040
If there's some other gap,
if it was five versus three,
00:43:45.040 --> 00:43:48.810
then we'd have beta equal two.
00:43:48.810 --> 00:43:50.240
Then there was the
other property,
00:43:50.240 --> 00:43:53.570
which is you need to show that
you don't blow up OPT too much.
00:43:53.570 --> 00:43:56.550
We want the OPT on
the right hand side
00:43:56.550 --> 00:43:59.880
to be at most some constant
times OPT on the left hand
00:43:59.880 --> 00:44:02.060
side.
00:44:02.060 --> 00:44:05.480
This requires a
little bit more care
00:44:05.480 --> 00:44:07.790
because we need to make sure
OPT is linear, basically.
00:44:07.790 --> 00:44:12.570
We did a lot of these
arguments last lecture.
00:44:12.570 --> 00:44:14.540
Because even when you
don't satisfy things,
00:44:14.540 --> 00:44:15.420
you still get points.
00:44:15.420 --> 00:44:19.180
And the difference between
zero and three is big ratio.
00:44:19.180 --> 00:44:20.942
We want that to not
happen too much.
00:44:20.942 --> 00:44:22.650
And it doesn't happen
too much because we
00:44:22.650 --> 00:44:28.640
know the left hand side OPT is
at least a half of all clauses.
00:44:28.640 --> 00:44:31.900
So it's not like there are
very many unsatisfied clauses.
00:44:31.900 --> 00:44:33.460
At most, half of
them are unsatisfied
00:44:33.460 --> 00:44:38.650
because at least half are
satisfiable in the case of OPT.
00:44:38.650 --> 00:44:42.570
So here's the full argument.
00:44:42.570 --> 00:44:49.430
00:44:49.430 --> 00:44:55.140
In general, OPT for
the 3SAT instance
00:44:55.140 --> 00:44:58.520
is going to be four times
all the satisfiable things
00:44:58.520 --> 00:45:00.780
plus three times all the
unsatisfiable things.
00:45:00.780 --> 00:45:06.100
This is the same thing
as saying the-- sorry.
00:45:06.100 --> 00:45:08.400
You take three times
the number of equations.
00:45:08.400 --> 00:45:11.590
Every equation gets
three points for free.
00:45:11.590 --> 00:45:15.030
And then if you also satisfy
them, you get one more point.
00:45:15.030 --> 00:45:18.900
So this is an equation on
those things, the two OPTs.
00:45:18.900 --> 00:45:21.430
And we get plus three times
the number of equations.
00:45:21.430 --> 00:45:24.590
And because there is a
one half approximation,
00:45:24.590 --> 00:45:31.170
we know that number of equations
is at most two times OPT.
00:45:31.170 --> 00:45:37.970
00:45:37.970 --> 00:45:40.800
Because OPT is at least a
half the number of equations.
00:45:40.800 --> 00:45:47.002
And so this thing is overall at
most six plus one seven times
00:45:47.002 --> 00:45:47.840
OPT E3 XNOR.
00:45:47.840 --> 00:45:52.760
00:45:52.760 --> 00:45:57.740
And this is the thing
called alpha in L-reduction.
00:45:57.740 --> 00:45:59.610
I wanted to compute
these explicitly
00:45:59.610 --> 00:46:02.310
because I want to see how
much inapproximability I get.
00:46:02.310 --> 00:46:05.425
Because I started with a
tight inapproximability bound
00:46:05.425 --> 00:46:08.720
of one half minus
epsilon being impossible,
00:46:08.720 --> 00:46:11.230
whereas one half is possible.
00:46:11.230 --> 00:46:16.600
It's tight up to this very tiny
arbitrary additive constant.
00:46:16.600 --> 00:46:19.450
And over here, we're
going to lose something.
00:46:19.450 --> 00:46:22.080
We know from L-reductions,
if you were inapproximable
00:46:22.080 --> 00:46:24.476
before, you get
inapproximability
00:46:24.476 --> 00:46:25.600
in this case of Max E3SAT.
00:46:25.600 --> 00:46:27.000
E3
00:46:27.000 --> 00:46:30.020
So what is the factor?
00:46:30.020 --> 00:46:33.750
If you think of-- there's
one simplification
00:46:33.750 --> 00:46:36.300
here relative to what
I presented before.
00:46:36.300 --> 00:46:38.900
A couple lectures ago, we
always thought about one
00:46:38.900 --> 00:46:43.370
plus epsilon approximation,
and how does epsilon change.
00:46:43.370 --> 00:46:46.020
And that works really well
for minimization problems.
00:46:46.020 --> 00:46:48.590
For a maximization problem,
your approximation factor
00:46:48.590 --> 00:46:53.140
is-- an approximation
factor of one
00:46:53.140 --> 00:46:56.640
plus epsilon means you are at
least this thing times OPT.
00:46:56.640 --> 00:47:00.500
And this thing gets
awkward to work with.
00:47:00.500 --> 00:47:03.300
Equivalently, with a
different notion of epsilon,
00:47:03.300 --> 00:47:06.760
you could just think of a one
minus epsilon approximation
00:47:06.760 --> 00:47:08.570
and how does epsilon change.
00:47:08.570 --> 00:47:12.310
And in general, for
maximization problem,
00:47:12.310 --> 00:47:15.110
if you have one minus
epsilon approximation
00:47:15.110 --> 00:47:17.600
before the L-reduction,
then afterwards you
00:47:17.600 --> 00:47:24.370
will have a one minus
epsilon over alpha beta.
00:47:24.370 --> 00:47:27.250
So for maximization, we
had one plus epsilon.
00:47:27.250 --> 00:47:29.770
And then we got one plus
epsilon over alpha beta.
00:47:29.770 --> 00:47:31.400
With the minuses,
it also works out.
00:47:31.400 --> 00:47:34.050
That's a cleaner way
to do maximization.
00:47:34.050 --> 00:47:35.530
So this was a
maximization problem.
00:47:35.530 --> 00:47:39.380
We had over here
epsilon was-- sorry,
00:47:39.380 --> 00:47:40.660
different notions of epsilon.
00:47:40.660 --> 00:47:43.680
Here we have one half
inapproximability
00:47:43.680 --> 00:47:46.280
One half is also known
as one minus one half.
00:47:46.280 --> 00:47:49.000
So epsilon here is a half.
00:47:49.000 --> 00:47:52.780
And alpha was seven.
00:47:52.780 --> 00:47:56.960
Beta was one.
00:47:56.960 --> 00:47:59.090
And so we just divide by seven.
00:47:59.090 --> 00:48:07.150
So in this case, we
get that Max E3SAT
00:48:07.150 --> 00:48:17.420
is one minus one half divided
by seven, which is 1/14.
00:48:17.420 --> 00:48:21.600
Technically there's
a minus epsilon here.
00:48:21.600 --> 00:48:24.059
Sorry, bad overuse of epsilon.
00:48:24.059 --> 00:48:26.100
This is, again, for any
epsilon greater than zero
00:48:26.100 --> 00:48:29.060
because we had some epsilon
greater than zero here.
00:48:29.060 --> 00:48:31.390
Slightly less than one
half is impossible.
00:48:31.390 --> 00:48:36.510
So over here we get slightly
less than one minus 1/14
00:48:36.510 --> 00:48:37.350
is impossible.
00:48:37.350 --> 00:48:50.530
This is 13/14 minus
epsilon, which is OK.
00:48:50.530 --> 00:48:51.870
It's a bound.
00:48:51.870 --> 00:48:53.590
But it's not a tight bound.
00:48:53.590 --> 00:48:57.210
The right answer
for Max 3SAT is 7/8.
00:48:57.210 --> 00:49:00.200
Because if you take, again,
a uniform random assignment,
00:49:00.200 --> 00:49:04.600
every variable flips a coin,
heads or tails, true or false.
00:49:04.600 --> 00:49:08.970
Then 7/8 of the clauses will
be satisfied in expectation.
00:49:08.970 --> 00:49:12.670
Because if you look at a clause,
if it has exactly three terms
00:49:12.670 --> 00:49:16.220
and it's an OR of three things,
you just need at least one head
00:49:16.220 --> 00:49:17.680
to satisfy this thing.
00:49:17.680 --> 00:49:20.270
So you get a 50% chance to
do it in the first time,
00:49:20.270 --> 00:49:22.478
and then a quarter chance
to do it in the third time,
00:49:22.478 --> 00:49:28.260
and in general 7/8 chance to
get it one of the three times.
00:49:28.260 --> 00:49:33.550
7/8 is smaller than 13/14,
so we're not quite there yet.
00:49:33.550 --> 00:49:37.560
But this reduction
will do it if we
00:49:37.560 --> 00:49:39.440
think about it from
the perspective
00:49:39.440 --> 00:49:41.890
of gap-preserving reductions.
00:49:41.890 --> 00:49:44.490
So from this general
L-reduction black box
00:49:44.490 --> 00:49:50.040
that we only lose an alpha beta
factor, yeah we get this bound.
00:49:50.040 --> 00:49:53.100
But from a gap perspective,
we can do better.
00:49:53.100 --> 00:49:56.000
The reason we can do better
is because gaps are always
00:49:56.000 --> 00:49:58.910
talking about yes instances
where lots of things
00:49:58.910 --> 00:49:59.612
are satisfied.
00:49:59.612 --> 00:50:02.070
That means we're most of the
time in the case where we have
00:50:02.070 --> 00:50:05.397
fours on the right hand side, or
a situation where we have lots
00:50:05.397 --> 00:50:07.730
of things unsatisfied, that
means we have lots of threes
00:50:07.730 --> 00:50:08.830
on the right hand side.
00:50:08.830 --> 00:50:11.730
It lets us get a
slightly tighter bound.
00:50:11.730 --> 00:50:12.530
So let's do that.
00:50:12.530 --> 00:50:33.840
00:50:33.840 --> 00:50:41.130
So here is a gap argument
about the same reduction.
00:50:41.130 --> 00:50:52.320
What we're going to claim is
that 7/8 minus epsilon gap 3SAT
00:50:52.320 --> 00:50:57.500
is NP-hard, which implies
7/8 inapproximability,
00:50:57.500 --> 00:50:59.540
but by looking at it
from the gap perspective,
00:50:59.540 --> 00:51:04.610
we will get this stronger
bound versus the 13/14 bound.
00:51:04.610 --> 00:51:09.930
So the proof is by a
gap-preserving reduction,
00:51:09.930 --> 00:51:18.300
namely that reduction, from
Max E3-XNOR-SAT to Max 3SAT,
00:51:18.300 --> 00:51:19.950
E3SAT I should say.
00:51:19.950 --> 00:51:23.490
00:51:23.490 --> 00:51:25.920
And so the idea
is the following.
00:51:25.920 --> 00:51:28.440
Either we have a yes
instance or a no instance.
00:51:28.440 --> 00:51:31.700
00:51:31.700 --> 00:51:38.440
If we have a yes instance
to the equation problem,
00:51:38.440 --> 00:51:45.510
then we know that at least one
minus epsilon of the equations
00:51:45.510 --> 00:51:48.150
are satisfiable.
00:51:48.150 --> 00:51:52.320
So we have one minus epsilon.
00:51:52.320 --> 00:51:53.945
Let's say m is the
number of equations.
00:51:53.945 --> 00:52:03.070
00:52:03.070 --> 00:52:04.530
In the no instance
case, of course
00:52:04.530 --> 00:52:06.910
we know that not too
many are satisfied.
00:52:06.910 --> 00:52:12.390
At most, one half plus epsilon
fraction of the equations
00:52:12.390 --> 00:52:13.750
are satisfiable.
00:52:13.750 --> 00:52:19.960
00:52:19.960 --> 00:52:24.560
So in both cases, I want to
see what that converts into.
00:52:24.560 --> 00:52:29.957
So in the yes instance,
we get all four
00:52:29.957 --> 00:52:33.190
of those things being satisfied.
00:52:33.190 --> 00:52:38.730
So that means we're going
to have at least one
00:52:38.730 --> 00:52:44.700
minus epsilon times m times
four clauses satisfied.
00:52:44.700 --> 00:52:47.960
We'll also have
epsilon m times three.
00:52:47.960 --> 00:52:49.425
Those are the unsatisfied.
00:52:49.425 --> 00:52:51.450
And maybe some of them
are actually satisfied,
00:52:51.450 --> 00:52:54.837
but this is a lower bound
on how many clauses we get.
00:52:54.837 --> 00:52:58.370
00:52:58.370 --> 00:53:00.690
On the other hand,
in this situation
00:53:00.690 --> 00:53:02.360
where not too many
are satisfied,
00:53:02.360 --> 00:53:04.560
that means we get a
tighter upper bound.
00:53:04.560 --> 00:53:13.520
So we have one half plus
epsilon times m times four.
00:53:13.520 --> 00:53:20.990
And then there's the rest, one
half minus epsilon times three.
00:53:20.990 --> 00:53:23.120
And maybe some of these
are not satisfied,
00:53:23.120 --> 00:53:27.590
but this is an upper bound on
how many clauses are satisfied
00:53:27.590 --> 00:53:32.170
in the 3SAT instance versus
equations in the 3x [INAUDIBLE]
00:53:32.170 --> 00:53:34.000
SAT instance.
00:53:34.000 --> 00:53:38.270
Now I just want
to compute these.
00:53:38.270 --> 00:53:40.540
So everything's times m.
00:53:40.540 --> 00:53:43.330
And over here we have
four minus four epsilon.
00:53:43.330 --> 00:53:46.350
Over here we have
plus three epsilon.
00:53:46.350 --> 00:53:50.890
So that is four minus epsilon m.
00:53:50.890 --> 00:53:53.920
And here we have again
everything is times m.
00:53:53.920 --> 00:54:02.460
So we have 4/2, also known
as two, plus four epsilon.
00:54:02.460 --> 00:54:04.970
00:54:04.970 --> 00:54:10.100
Plus we have 3/2
minus three epsilon.
00:54:10.100 --> 00:54:12.305
So the epsilons add
up to plus epsilon.
00:54:12.305 --> 00:54:13.180
Then I check and see.
00:54:13.180 --> 00:54:16.250
Four epsilon minus
three epsilon.
00:54:16.250 --> 00:54:21.871
And then we have 4/2 plus
3/2, also known as 7/2.
00:54:21.871 --> 00:54:22.370
Yes.
00:54:22.370 --> 00:54:30.620
00:54:30.620 --> 00:54:36.020
So we had a gap before, and
we get this new gap after.
00:54:36.020 --> 00:54:37.635
When we have a yes
instance, we know
00:54:37.635 --> 00:54:39.510
that there will be at
least this many clauses
00:54:39.510 --> 00:54:41.150
satisfied in the 3SAT.
00:54:41.150 --> 00:54:44.020
And there'll be at most this
many in the no instance.
00:54:44.020 --> 00:54:51.840
So what we proved is
this bound that-- sorry,
00:54:51.840 --> 00:54:53.060
get them in the right order.
00:54:53.060 --> 00:54:55.240
7/2 is the smaller one.
00:54:55.240 --> 00:55:04.220
7/2 plus epsilon, comma
four minus epsilon gap 3SAT,
00:55:04.220 --> 00:55:10.020
E3SAT, is NP-hard.
00:55:10.020 --> 00:55:13.490
Because we had NP hardness
of the gap before,
00:55:13.490 --> 00:55:15.070
we did this
gap-preserving reduction,
00:55:15.070 --> 00:55:17.287
which ended up
with this new gap,
00:55:17.287 --> 00:55:19.120
with this being for no
instances, this being
00:55:19.120 --> 00:55:21.140
for yes instances.
00:55:21.140 --> 00:55:24.010
And so if we want to-- this
is with the comma notation
00:55:24.010 --> 00:55:27.600
for the yes and no what
fraction is satisfied.
00:55:27.600 --> 00:55:32.870
If you convert it back
into the c gap notation,
00:55:32.870 --> 00:55:35.380
you just take the ratio
between these two things.
00:55:35.380 --> 00:55:40.690
And ignoring the epsilons,
this is like 4 divided by 7/2.
00:55:40.690 --> 00:55:48.640
So that is 7/8 or 8/7, depending
on which way you're looking.
00:55:48.640 --> 00:55:54.580
So we get also 7/8 gap.
00:55:54.580 --> 00:56:01.090
Sorry, I guess it's 8/7 the
way I was phrasing it before.
00:56:01.090 --> 00:56:02.700
It's also NP-hard.
00:56:02.700 --> 00:56:05.494
And so that proves-- there's
also a minus epsilon.
00:56:05.494 --> 00:56:06.660
So I should have kept those.
00:56:06.660 --> 00:56:10.880
Slightly different epsilon, but
minus two epsilon, whatever.
00:56:10.880 --> 00:56:14.300
And so this gives us the 8/7
is the best approximation
00:56:14.300 --> 00:56:15.680
factor we can hope for.
00:56:15.680 --> 00:56:17.300
AUDIENCE: In the
first notation, isn't
00:56:17.300 --> 00:56:18.852
it the fraction of clauses?
00:56:18.852 --> 00:56:21.377
So between zero and one?
00:56:21.377 --> 00:56:22.210
PROFESSOR: Oh, yeah.
00:56:22.210 --> 00:56:24.020
Four is a little funny.
00:56:24.020 --> 00:56:24.520
Right.
00:56:24.520 --> 00:56:29.100
I needed to scale-- thank you--
because the number of clauses
00:56:29.100 --> 00:56:31.470
in the resulting thing
is actually 4m, not m.
00:56:31.470 --> 00:56:35.490
So everything here needs
to be divided by four.
00:56:35.490 --> 00:56:38.450
It won't affect the final
ratio, but this should really
00:56:38.450 --> 00:56:42.550
be over four and over four.
00:56:42.550 --> 00:56:51.690
So also known as
7/8 plus epsilon,
00:56:51.690 --> 00:56:54.690
comma one minus epsilon.
00:56:54.690 --> 00:56:57.970
Now it's a little clearer, 7/8.
00:56:57.970 --> 00:57:00.760
Cool.
00:57:00.760 --> 00:57:01.752
Yeah.
00:57:01.752 --> 00:57:06.720
AUDIENCE: So are there any
CSPs where we can beat randomness?
00:57:06.720 --> 00:57:10.970
AUDIENCE: So for Max Cut,
you can beat the randomness.
00:57:10.970 --> 00:57:13.280
Randomness would
give you one half.
00:57:13.280 --> 00:57:16.526
The Goemans-Williamson
algorithm gives you 1.8.
00:57:16.526 --> 00:57:18.650
PROFESSOR: So you can beat
it by a constant factor.
00:57:18.650 --> 00:57:20.840
Probably not by more
than a constant factor.
00:57:20.840 --> 00:57:24.780
Max Cut is an example
where you can beat it.
00:57:24.780 --> 00:57:28.220
I think I have the Goemans-
Williamson bound here.
00:57:28.220 --> 00:57:31.770
00:57:31.770 --> 00:57:33.860
Max Cut, the best
approximation is
00:57:33.860 --> 00:57:37.690
0.878, which is better than
what you get by random,
00:57:37.690 --> 00:57:40.120
which is a half I guess.
00:57:40.120 --> 00:57:42.370
Cool.
00:57:42.370 --> 00:57:42.870
All right.
00:57:42.870 --> 00:57:45.240
00:57:45.240 --> 00:57:45.740
Cool.
00:57:45.740 --> 00:57:48.850
So we get optimal
bound for Max E3SAT,
00:57:48.850 --> 00:57:53.251
assuming an optimum bound for
E3-XNOR-SAT, which is from PCP.
00:57:53.251 --> 00:57:53.750
Yeah.
00:57:53.750 --> 00:57:55.500
AUDIENCE: So I'm sorry, can
you explain to me again why
00:57:55.500 --> 00:57:57.145
we don't get this
from the L-reduction,
00:57:57.145 --> 00:57:58.770
but we do get it from
the gap argument,
00:57:58.770 --> 00:58:01.010
even though the reduction
is the same reduction?
00:58:01.010 --> 00:58:03.649
PROFESSOR: It just lets
us give a tighter argument
00:58:03.649 --> 00:58:04.190
in this case.
00:58:04.190 --> 00:58:07.300
By thinking about yes instances
and no instances separately,
00:58:07.300 --> 00:58:08.820
we get one thing.
00:58:08.820 --> 00:58:12.320
Because this reduction is
designed to do different things
00:58:12.320 --> 00:58:13.854
for yes and no instances.
00:58:13.854 --> 00:58:15.770
Whereas the L-reduction
just says generically,
00:58:15.770 --> 00:58:18.650
if you satisfy these
parameters alpha and beta,
00:58:18.650 --> 00:58:20.960
you get some inapproximability
result on the output,
00:58:20.960 --> 00:58:22.970
but it's conservative.
00:58:22.970 --> 00:58:24.110
It's a conservative bound.
00:58:24.110 --> 00:58:26.500
If you just use properties
one and two up here,
00:58:26.500 --> 00:58:28.150
that's the best you could show.
00:58:28.150 --> 00:58:32.614
But by essentially
reanalyzing property one,
00:58:32.614 --> 00:58:34.780
but thinking separately
about yes and no instances--
00:58:34.780 --> 00:58:36.870
this held for all instances.
00:58:36.870 --> 00:58:38.510
We got a bound of seven.
00:58:38.510 --> 00:58:40.205
But in the yes and
the no cases, you
00:58:40.205 --> 00:58:42.205
can essentially get a
slightly tighter constant.
00:58:42.205 --> 00:58:46.041
00:58:46.041 --> 00:58:46.540
All right.
00:58:46.540 --> 00:58:50.500
I want to tell you about
another cool problem.
00:58:50.500 --> 00:59:08.490
00:59:08.490 --> 00:59:22.540
Another gap hardness that you
can get out of PCP analysis
00:59:22.540 --> 00:59:28.590
by some gap amplification
essentially, which
00:59:28.590 --> 00:59:29.560
is called label cover.
00:59:29.560 --> 00:59:36.610
00:59:36.610 --> 00:59:40.970
So this problem takes a
little bit of time to define.
00:59:40.970 --> 00:59:44.520
But the basic point is there
are very strong lower bounds
00:59:44.520 --> 00:59:45.770
on the approximation factor.
00:59:45.770 --> 01:00:02.530
01:00:02.530 --> 01:00:04.800
So you're given a bipartite
graph, no weights.
01:00:04.800 --> 01:00:09.180
01:00:09.180 --> 01:00:14.120
The bipartition is A,
B. And furthermore, A
01:00:14.120 --> 01:00:16.995
can be divided into k chunks.
01:00:16.995 --> 01:00:20.620
01:00:20.620 --> 01:00:28.015
And so can B. And these
are disjoint unions.
01:00:28.015 --> 01:00:30.620
01:00:30.620 --> 01:00:37.980
And let's say size of
A is n, size of B is n,
01:00:37.980 --> 01:00:44.510
and size of each A_i
is also the same.
01:00:44.510 --> 01:00:48.236
We don't have to make these
assumptions, but you can.
01:00:48.236 --> 01:00:50.170
So let's make it a
little bit cleaner.
01:00:50.170 --> 01:00:53.840
So in general, A consists of k
groups, each of size n over k.
01:00:53.840 --> 01:00:57.970
B consists of k groups,
each of size n over k.
01:00:57.970 --> 01:01:02.510
So that's our-- we have A
here with these little groups.
01:01:02.510 --> 01:01:06.060
We have B, these little groups.
01:01:06.060 --> 01:01:07.560
And there's some
edges between them.
01:01:07.560 --> 01:01:14.200
01:01:14.200 --> 01:01:20.390
In general, your goal is
to choose some subset of A,
01:01:20.390 --> 01:01:26.400
let's call it A', and some
subset of B, call it B'.
01:01:26.400 --> 01:01:32.180
And one other thing
I want to talk about
01:01:32.180 --> 01:01:34.180
is called a super edge.
01:01:34.180 --> 01:01:39.050
01:01:39.050 --> 01:01:41.780
And then I'll say what we
want out of these subsets
01:01:41.780 --> 01:01:43.220
that we choose.
01:01:43.220 --> 01:01:46.330
Imagine contracting
each of these groups.
01:01:46.330 --> 01:01:49.750
There are n over k
items here, and there
01:01:49.750 --> 01:01:52.830
are k different groups.
01:01:52.830 --> 01:01:56.700
Imagine contracting each
group to a single vertex.
01:01:56.700 --> 01:01:58.670
This is A_1.
01:01:58.670 --> 01:02:01.810
This is B_3.
01:02:01.810 --> 01:02:04.320
I want to say that there's
a super edge from the group
01:02:04.320 --> 01:02:06.290
A_1 to the group
B_3 because there's
01:02:06.290 --> 01:02:08.290
at least one edge between them.
01:02:08.290 --> 01:02:10.390
If I squashed A_1
to a single vertex,
01:02:10.390 --> 01:02:13.610
B_3 down to a single vertex, I
would get an edge between them.
01:02:13.610 --> 01:02:21.600
So a super edge, A_i, B_i--
A_i, B_j, I should say--
01:02:21.600 --> 01:02:26.610
exists if there's
at least one edge
01:02:26.610 --> 01:02:33.340
in A_i cross B_j, at least one
edge connecting those groups.
01:02:33.340 --> 01:02:38.610
And I'm going to call such a
super edge covered by (A', B')
01:02:38.610 --> 01:02:46.410
if at least one of those
edges is in this chosen set.
01:02:46.410 --> 01:02:49.452
So if there's at least
one edge-- sorry.
01:02:49.452 --> 01:02:52.650
01:02:52.650 --> 01:02:57.590
If this A_i cross B_j, these
are all the possible edges
01:02:57.590 --> 01:03:10.420
between those groups, intersects
A' cross B'.
01:03:10.420 --> 01:03:13.820
And in general, I want to cover
all the hyper edges if I can.
01:03:13.820 --> 01:03:16.960
So I would like to
have a solution where,
01:03:16.960 --> 01:03:20.570
if there is some edge
between A_1 and B_3,
01:03:20.570 --> 01:03:23.430
then in the set of
vertices I choose,
01:03:23.430 --> 01:03:28.100
A' and B' in the left,
they induce at least one edge
01:03:28.100 --> 01:03:31.480
from A_1 to B_3, and
also from A_2 to B_3
01:03:31.480 --> 01:03:34.400
because there is an
edge that I drew here.
01:03:34.400 --> 01:03:37.197
I want ideally to choose
the endpoints of that edge,
01:03:37.197 --> 01:03:39.280
or some other edge that
connects those two groups.
01:03:39.280 --> 01:03:39.625
Yeah.
01:03:39.625 --> 01:03:41.810
AUDIENCE: So you're choosing
subsets A' of A.
01:03:41.810 --> 01:03:43.934
Is there some restriction
on the subset you choose?
01:03:43.934 --> 01:03:45.379
Why don't you choose all of A?
01:03:45.379 --> 01:03:46.045
PROFESSOR: Wait.
01:03:46.045 --> 01:03:46.793
AUDIENCE: Oh, OK.
01:03:46.793 --> 01:03:48.300
You're not done yet?
01:03:48.300 --> 01:03:50.595
PROFESSOR: Nope.
01:03:50.595 --> 01:03:52.095
That's about half
of the definition.
01:03:52.095 --> 01:03:59.690
01:03:59.690 --> 01:04:02.630
it's a lot to say it's not
that complicated of a problem.
01:04:02.630 --> 01:04:07.300
01:04:07.300 --> 01:04:09.680
So there's two versions.
01:04:09.680 --> 01:04:11.910
That's part of what
makes it longer.
01:04:11.910 --> 01:04:13.850
We'll start with the
maximization version,
01:04:13.850 --> 01:04:16.020
which is called Max-Rep.
01:04:16.020 --> 01:04:19.380
So we have two constraints
on A' and B'.
01:04:19.380 --> 01:04:23.520
01:04:23.520 --> 01:04:26.680
First is that we choose exactly
one vertex from each group.
01:04:26.680 --> 01:04:34.200
01:04:34.200 --> 01:04:39.420
So we got |A' intersect A_i|
equals one,
01:04:39.420 --> 01:04:48.100
and |B' intersect B_j|
equals one, for all i and j.
01:04:48.100 --> 01:04:52.220
OK And then subject
to that constraint,
01:04:52.220 --> 01:04:56.880
we want to maximize the
number of covered super edges.
01:04:56.880 --> 01:05:04.640
01:05:04.640 --> 01:05:09.750
Intuition here is that
those groups are labels.
01:05:09.750 --> 01:05:11.940
And there's really one
super vertex there,
01:05:11.940 --> 01:05:14.360
and you want to choose
one of those labels
01:05:14.360 --> 01:05:16.220
to satisfy the instance.
01:05:16.220 --> 01:05:18.880
So here you're only allowed to
choose one label per vertex.
01:05:18.880 --> 01:05:21.360
We choose one out of
each of the groups.
01:05:21.360 --> 01:05:24.830
Then you'd like to cover
as many edges as you can.
01:05:24.830 --> 01:05:30.236
If there is an edge in the
super graph from A_i to B_j,
01:05:30.236 --> 01:05:34.337
you would like to
include an induced edge.
01:05:34.337 --> 01:05:36.420
There should actually be
an edge between the label
01:05:36.420 --> 01:05:40.020
you assign to A_i and the
label you assign to B_j.
01:05:40.020 --> 01:05:42.190
That's this version.
01:05:42.190 --> 01:05:45.560
The complementary problem
is a minimization problem
01:05:45.560 --> 01:05:49.900
where we switch what is relaxed,
what constraint is relaxed,
01:05:49.900 --> 01:05:52.490
and what constraint must hold.
01:05:52.490 --> 01:05:55.770
So here we're going to
allow multiple labels
01:05:55.770 --> 01:05:58.480
for each super vertex,
multiple vertices
01:05:58.480 --> 01:06:01.060
to be chosen from each group.
01:06:01.060 --> 01:06:05.470
Instead we force that
everything is covered.
01:06:05.470 --> 01:06:15.720
We want to cover every
super edge that exists.
01:06:15.720 --> 01:06:22.210
And our goal is to minimize
the size of these sets,
01:06:22.210 --> 01:06:25.060
|A'| plus |B'|.
01:06:25.060 --> 01:06:27.820
So this is sort of
the dual problem.
01:06:27.820 --> 01:06:29.359
Here we force one
level per vertex.
01:06:29.359 --> 01:06:31.400
We want to maximize the
number of covered things.
01:06:31.400 --> 01:06:33.160
Here we force everything
to be covered.
01:06:33.160 --> 01:06:36.582
We want to essentially minimize
the number of labels we assign.
01:06:36.582 --> 01:06:39.560
01:06:39.560 --> 01:06:42.480
So these problems
are both very hard.
01:06:42.480 --> 01:06:46.040
This should build you
some more intuition.
01:06:46.040 --> 01:06:49.860
Let me show you a puzzle
which is basically
01:06:49.860 --> 01:06:55.600
exactly this game, designed by
MIT professor Dana Moshkovitz.
01:06:55.600 --> 01:06:58.610
So here's a word puzzle.
01:06:58.610 --> 01:07:01.480
Your goal is to put letters
into each of these boxes-- this
01:07:01.480 --> 01:07:06.760
is B, and this is A-- such
that-- for example, this
01:07:06.760 --> 01:07:10.240
is animal, which means
these three things pointed
01:07:10.240 --> 01:07:13.910
by the red arrows, those
letters should concatenate
01:07:13.910 --> 01:07:17.980
to form an animal, like cat.
01:07:17.980 --> 01:07:20.340
Bat is the example.
01:07:20.340 --> 01:07:24.530
So if I write B, A, and T,
animal is satisfied perfectly.
01:07:24.530 --> 01:07:27.960
Because all three
letters form a word,
01:07:27.960 --> 01:07:31.090
I get three points so far.
01:07:31.090 --> 01:07:33.790
Next let's think
about transportation.
01:07:33.790 --> 01:07:35.680
For example, cab is
a three-letter word
01:07:35.680 --> 01:07:36.910
that is transportation.
01:07:36.910 --> 01:07:38.700
Notice there's always
three over here.
01:07:38.700 --> 01:07:44.370
This corresponds to some
regularity constraint
01:07:44.370 --> 01:07:45.710
on the bipartite graph.
01:07:45.710 --> 01:07:48.510
There's always going to be three
arrows going from left to right
01:07:48.510 --> 01:07:53.460
for every group.
01:07:53.460 --> 01:07:55.050
So transportation, fine.
01:07:55.050 --> 01:07:59.130
We got C-A-B. That is happy.
01:07:59.130 --> 01:08:01.830
We happen to reuse the A,
so we get three more points,
01:08:01.830 --> 01:08:03.189
total of six.
01:08:03.189 --> 01:08:08.720
Furniture, we have
B, blank, and T left.
01:08:08.720 --> 01:08:10.220
This is going to
be a little harder.
01:08:10.220 --> 01:08:12.220
I don't know of any
furniture that starts with B
01:08:12.220 --> 01:08:14.660
and ends with T and
is three letters long.
01:08:14.660 --> 01:08:17.450
But if you, for example,
write an E here,
01:08:17.450 --> 01:08:20.505
that's pretty close to the
word bed, which is furniture.
01:08:20.505 --> 01:08:22.380
So in general, of course,
each of these words
01:08:22.380 --> 01:08:25.080
corresponds to a set
of English words.
01:08:25.080 --> 01:08:28.790
That's going to be the
groups on the left.
01:08:28.790 --> 01:08:31.130
So this A_i group
for furniture is
01:08:31.130 --> 01:08:33.729
the set of all words that are
furniture and three letters
01:08:33.729 --> 01:08:35.649
long.
01:08:35.649 --> 01:08:38.604
And then for each such
choice on the left,
01:08:38.604 --> 01:08:40.020
for each such
choice on the right,
01:08:40.020 --> 01:08:41.478
you can say is,
are they compatible
01:08:41.478 --> 01:08:44.680
by either putting
an edge or not.
01:08:44.680 --> 01:08:48.800
And so this is-- we got two
out of three of these edges.
01:08:48.800 --> 01:08:50.149
These two are satisfied.
01:08:50.149 --> 01:08:50.830
This one's not.
01:08:50.830 --> 01:08:54.599
So we get two more points
for a total of eight.
01:08:54.599 --> 01:08:56.140
This is for the
maximization problem.
01:08:56.140 --> 01:08:59.330
Minimization would be different.
01:08:59.330 --> 01:09:03.609
Here's a verb, where we
almost get cry, C-B-Y.
01:09:03.609 --> 01:09:06.100
So we get two more points.
01:09:06.100 --> 01:09:07.370
Here is another.
01:09:07.370 --> 01:09:08.670
We want a verb.
01:09:08.670 --> 01:09:12.770
Blank, A, Y. There are
multiple such verbs.
01:09:12.770 --> 01:09:14.420
You can think of them.
01:09:14.420 --> 01:09:17.300
And on the other hand,
we have a food, which
01:09:17.300 --> 01:09:21.470
is supposed to be blank, E,
Y. So a pretty good choice
01:09:21.470 --> 01:09:23.029
would be P for that top letter.
01:09:23.029 --> 01:09:26.300
Then you get pay exactly
and almost get pea.
01:09:26.300 --> 01:09:29.010
So a total score of 15.
01:09:29.010 --> 01:09:35.085
And so this would be a
solution to Max-Rep of cost 15.
01:09:35.085 --> 01:09:36.775
It's not the best.
01:09:36.775 --> 01:09:38.650
And if you stare at this
example long enough,
01:09:38.650 --> 01:09:42.130
you can actually get a perfect
solution of score 18, where
01:09:42.130 --> 01:09:43.130
there are no violations.
01:09:43.130 --> 01:09:48.940
Basically, in particular you do
say here and get soy for food.
01:09:48.940 --> 01:09:52.515
AUDIENCE: So the sets on
the right are 26 letters?
01:09:52.515 --> 01:09:53.140
PROFESSOR: Yes.
01:09:53.140 --> 01:09:56.260
The B_i's here are the
alphabet A through Z,
01:09:56.260 --> 01:09:58.519
and the sets on the
left are a set of words.
01:09:58.519 --> 01:10:00.810
And then you're going to
connect two of them by an edge
01:10:00.810 --> 01:10:07.030
if that letter happens to
match on the right, the ith
01:10:07.030 --> 01:10:08.160
letter.
01:10:08.160 --> 01:10:10.150
So it's a little--
I mean, the mapping
01:10:10.150 --> 01:10:11.150
is slightly complicated.
01:10:11.150 --> 01:10:13.930
But this is a particular
instance of Max-Rep.
01:10:13.930 --> 01:10:17.580
01:10:17.580 --> 01:10:25.930
So what-- well, we get
some super extreme hardness
01:10:25.930 --> 01:10:27.760
for these problems.
01:10:27.760 --> 01:10:42.210
So let's start with epsilon,
comma one gap Max-Rep
01:10:42.210 --> 01:10:42.850
is NP-hard.
01:10:42.850 --> 01:10:52.660
01:10:52.660 --> 01:10:57.000
So what I mean by this
is in the best situation,
01:10:57.000 --> 01:10:59.360
you cover all of
the super edges.
01:10:59.360 --> 01:11:02.521
So the one means 100% of
the super edges are covered.
01:11:02.521 --> 01:11:04.770
Epsilon means that at most
an epsilon fraction of them
01:11:04.770 --> 01:11:05.670
are covered.
01:11:05.670 --> 01:11:06.797
So that problem is NP-hard.
01:11:06.797 --> 01:11:08.755
This is a bit stronger
than what we had before.
01:11:08.755 --> 01:11:12.770
Before we had a particular
constant, comma one or one
01:11:12.770 --> 01:11:14.700
minus epsilon or something.
01:11:14.700 --> 01:11:17.670
Here, for any constant
epsilon, this is true.
01:11:17.670 --> 01:11:20.342
01:11:20.342 --> 01:11:22.050
And there's a similar
result for Min-Rep.
01:11:22.050 --> 01:11:25.660
It's just from one
to one over epsilon.
01:11:25.660 --> 01:11:28.370
So this means there is no
constant factor approximation.
01:11:28.370 --> 01:11:31.990
Max-Rep is not in APX.
01:11:31.990 --> 01:11:33.960
But it's worse than that.
01:11:33.960 --> 01:11:38.080
We need to assume slightly more.
01:11:38.080 --> 01:11:44.836
In general, what you can show,
if you have some constant, p,
01:11:44.836 --> 01:11:55.430
or there is a constant p, such
that if you can solve this gap
01:11:55.430 --> 01:11:59.200
problem, one over p to the k,
so very tiny fraction of things
01:11:59.200 --> 01:12:02.090
satisfied versus all
of the super edges
01:12:02.090 --> 01:12:13.840
covered, then NP can be solved
in n to the order k time.
01:12:13.840 --> 01:12:18.800
01:12:18.800 --> 01:12:20.970
So we haven't usually
used this class.
01:12:20.970 --> 01:12:23.730
Usually we talk about P, which
is the union of all these
01:12:23.730 --> 01:12:24.942
for constant k.
01:12:24.942 --> 01:12:26.650
But here k doesn't
have to be a constant.
01:12:26.650 --> 01:12:28.680
It could be some function of n.
01:12:28.680 --> 01:12:31.140
And in particular, if
P does not equal NP,
01:12:31.140 --> 01:12:33.810
then k constant is not possible.
01:12:33.810 --> 01:12:36.805
So this result
implies this result.
01:12:36.805 --> 01:12:39.670
01:12:39.670 --> 01:12:46.070
But if we let k get bigger
than a constant, like log-log n
01:12:46.070 --> 01:12:52.070
or something, then we get
some separation between-- we
01:12:52.070 --> 01:12:54.670
get a somewhat weaker
statement here.
01:12:54.670 --> 01:12:56.970
We know if P does
not equal NP, we know
01:12:56.970 --> 01:12:59.500
that NP is not contained in P.
01:12:59.500 --> 01:13:02.880
But if we furthermore
assume that NP doesn't
01:13:02.880 --> 01:13:08.470
have subexponential solutions,
and very subexponential
01:13:08.470 --> 01:13:11.190
solutions, then we
get various gap bounds
01:13:11.190 --> 01:13:12.960
inapproximability on Max-Rep.
01:13:12.960 --> 01:13:16.420
So a reasonable
limit, for example,
01:13:16.420 --> 01:13:29.560
is that-- let's say we assume
NP is not in n to the polylog n.
01:13:29.560 --> 01:13:32.836
01:13:32.836 --> 01:13:36.260
n to the polylog n is usually
called quasi-polynomial.
01:13:36.260 --> 01:13:37.790
It's almost polynomial.
01:13:37.790 --> 01:13:41.370
Log n is kind of close
to constant-- ish.
01:13:41.370 --> 01:13:45.487
This is the same as two to the
polylog n, n to the polylog n.
01:13:45.487 --> 01:13:46.570
But it's a little clearer.
01:13:46.570 --> 01:13:50.200
This is obviously close
to polynomial, quite far
01:13:50.200 --> 01:13:53.750
from exponential, which is
two to the n, not polylog.
01:13:53.750 --> 01:13:55.300
So very different
from exponential.
01:13:55.300 --> 01:13:59.890
So almost everyone
believes NP does not admit
01:13:59.890 --> 01:14:01.050
quasi-polynomial solutions.
01:14:01.050 --> 01:14:03.390
All problems in NP would
have to admit that.
01:14:03.390 --> 01:14:05.066
3SAT, for example,
people don't think
01:14:05.066 --> 01:14:06.982
you can do better than
some constant to the n.
01:14:06.982 --> 01:14:09.650
01:14:09.650 --> 01:14:15.530
Then what do we get when
we plug in that value of k?
01:14:15.530 --> 01:14:23.890
That there is a no 1/2 to the
log to the one minus epsilon
01:14:23.890 --> 01:14:26.045
n approximation.
01:14:26.045 --> 01:14:28.700
01:14:28.700 --> 01:14:32.580
Or also, the same
thing, gap is hard.
01:14:32.580 --> 01:14:34.460
Now, it's not NP-hard.
01:14:34.460 --> 01:14:35.919
But it's as hard
as this problem.
01:14:35.919 --> 01:14:37.710
If you believe this is
not true, then there
01:14:37.710 --> 01:14:39.330
will be no polynomial
time algorithm
01:14:39.330 --> 01:14:43.030
to solve this
factor gap Max-Rep.
01:14:43.030 --> 01:14:44.390
So this is very large.
01:14:44.390 --> 01:14:48.925
We've seen this before in
this table of various results.
01:14:48.925 --> 01:14:51.300
Near the bottom, there is a
lower bound of two to the log
01:14:51.300 --> 01:14:52.740
to one minus epsilon n.
01:14:52.740 --> 01:14:55.130
This is not assuming
P does not equal NP.
01:14:55.130 --> 01:14:57.220
It's assuming this
statement, NP does not
01:14:57.220 --> 01:14:59.760
have quasi-polynomial
algorithms.
01:14:59.760 --> 01:15:01.600
And you see here
our friends Max-Rep
01:15:01.600 --> 01:15:05.250
and Min-Rep, two
versions of label cover.
01:15:05.250 --> 01:15:09.190
So I'm not going to
prove these theorems.
01:15:09.190 --> 01:15:11.670
But again, they're
PCP style arguments
01:15:11.670 --> 01:15:15.390
with some gap boosting.
01:15:15.390 --> 01:15:20.350
But I would say most or a
lot of approximation lower
01:15:20.350 --> 01:15:24.400
bounds in the world today
start from Max-Rep or Min-Rep
01:15:24.400 --> 01:15:27.520
and reduce to the problem
using usually some kind
01:15:27.520 --> 01:15:29.350
of gap-preserving reduction.
01:15:29.350 --> 01:15:31.520
Maybe they lose the gap,
but we have such a huge gap
01:15:31.520 --> 01:15:33.330
to start with that
even if you lose gap,
01:15:33.330 --> 01:15:35.990
you still get
pretty good results.
01:15:35.990 --> 01:15:39.650
So a couple of quick
examples here on the slides.
01:15:39.650 --> 01:15:41.610
Directed Steiner forest.
01:15:41.610 --> 01:15:43.700
Remember, you have
a directed graph,
01:15:43.700 --> 01:15:46.860
and you have a bunch
of terminal pairs.
01:15:46.860 --> 01:15:50.710
And you want to, in particular,
connect via directed path
01:15:50.710 --> 01:15:54.490
some A_i's and B_j's, let's say.
01:15:54.490 --> 01:15:58.550
And you want to do so by
choosing the fewest vertices
01:15:58.550 --> 01:15:59.970
in this graph.
01:15:59.970 --> 01:16:04.060
So what I'm going to do, if I'm
given my bipartite graph here
01:16:04.060 --> 01:16:06.404
for Min-Rep, I'm
just going to add--
01:16:06.404 --> 01:16:07.820
to represent that
this is a group,
01:16:07.820 --> 01:16:10.790
I'm going to add a vertex here
connect by directed edges here.
01:16:10.790 --> 01:16:12.370
And there's a group
down here, so I'm
01:16:12.370 --> 01:16:14.360
going to have downward
edges down there.
01:16:14.360 --> 01:16:17.350
And whenever there's a
super edge from, say,
01:16:17.350 --> 01:16:20.480
A_2, capital A_2 to
capital B_1, then
01:16:20.480 --> 01:16:23.010
I'm going to say in my directed
Steiner forest problem,
01:16:23.010 --> 01:16:26.426
I want a path from
little a_2 to little b_1.
01:16:26.426 --> 01:16:28.300
So in general, whenever
there's a super edge,
01:16:28.300 --> 01:16:29.960
I add that constraint.
01:16:29.960 --> 01:16:32.520
And then any solution to
directed Steiner forest
01:16:32.520 --> 01:16:34.530
will exactly be a
solution to Min-Rep.
01:16:34.530 --> 01:16:38.540
You're just forcing the
addition of the A_i's and B_i's.
01:16:38.540 --> 01:16:40.060
It's again an L-reduction.
01:16:40.060 --> 01:16:42.380
You're just offsetting by
a fixed additive amount.
01:16:42.380 --> 01:16:44.291
So your gap OPT
will be the same.
01:16:44.291 --> 01:16:46.790
And so you get that this problem
is just as hard as Min-Rep.
01:16:46.790 --> 01:16:52.370
01:16:52.370 --> 01:16:54.540
Well, this is another
one from set cover.
01:16:54.540 --> 01:16:57.450
You can also show node
weighted Steiner trees.
01:16:57.450 --> 01:16:58.910
Log n hard to approximate.
01:16:58.910 --> 01:17:01.750
That's not from Min-Rep,
but threw it in there
01:17:01.750 --> 01:17:04.161
while we're on the
topic of Steiner trees.
01:17:04.161 --> 01:17:04.660
All right.
01:17:04.660 --> 01:17:08.297
I want to mention one
more thing quickly
01:17:08.297 --> 01:17:09.505
in my zero minutes remaining.
01:17:09.505 --> 01:17:22.030
01:17:22.030 --> 01:17:25.400
And that is unique games.
01:17:25.400 --> 01:17:31.000
01:17:31.000 --> 01:17:34.530
So unique games is a
special case of, say,
01:17:34.530 --> 01:17:45.420
Max-Rep, or either label cover
problem, where the edges in A_i
01:17:45.420 --> 01:17:48.927
cross B_j form a matching.
01:17:48.927 --> 01:17:54.280
01:17:54.280 --> 01:17:56.310
For every choice in
the left, there's
01:17:56.310 --> 01:18:01.620
a unique choice on the right
and vice versa that matches.
01:18:01.620 --> 01:18:03.670
Well, there's at most
one choice, I guess.
01:18:03.670 --> 01:18:07.460
And I think that
corresponds to these games.
01:18:07.460 --> 01:18:09.340
Once you choose
a word over here,
01:18:09.340 --> 01:18:10.990
there's unique
letter that matches.
01:18:10.990 --> 01:18:12.680
The reverse is not true.
01:18:12.680 --> 01:18:15.000
So in this problem,
it's more like a star,
01:18:15.000 --> 01:18:15.850
left to right star.
01:18:15.850 --> 01:18:18.480
Once you choose this
word, it's fixed
01:18:18.480 --> 01:18:20.230
what you have to choose
on the right side.
01:18:20.230 --> 01:18:22.063
But if you choose a
single letter over here,
01:18:22.063 --> 01:18:24.150
it does not uniquely
determine the word over here.
01:18:24.150 --> 01:18:26.130
So unique games is
quite a bit stronger.
01:18:26.130 --> 01:18:28.130
You choose either side,
it forces the other one,
01:18:28.130 --> 01:18:31.140
if you want to cover that edge.
01:18:31.140 --> 01:18:35.370
OK. So far so good.
01:18:35.370 --> 01:18:40.250
Unique games conjecture is that
the special case is also hard.
01:18:40.250 --> 01:18:50.690
Unique games conjecture is that
(epsilon, one minus epsilon) gap
01:18:50.690 --> 01:18:54.951
unique game is NP-hard.
01:18:54.951 --> 01:18:56.450
Of course, there
are weaker versions
01:18:56.450 --> 01:18:58.417
of this conjecture
that don't say NP-hard,
01:18:58.417 --> 01:19:00.500
maybe assuming some weaker
assumption that there's
01:19:00.500 --> 01:19:03.850
no polynomial time algorithm.
01:19:03.850 --> 01:19:06.530
Unlike every other complexity
theoretic assumption
01:19:06.530 --> 01:19:08.460
I have mentioned in
this class, this one
01:19:08.460 --> 01:19:10.100
is the subject of much debate.
01:19:10.100 --> 01:19:11.820
Not everyone believes
that it's true.
01:19:11.820 --> 01:19:13.880
Some people believe
that it's false.
01:19:13.880 --> 01:19:16.800
Many people believe--
basically people don't know
01:19:16.800 --> 01:19:17.980
is the short answer.
01:19:17.980 --> 01:19:21.585
There's some somewhat scary
evidence that it's not true.
01:19:21.585 --> 01:19:24.210
There's slightly stronger forms
of this that are definitely not
01:19:24.210 --> 01:19:26.640
true, which I won't get into.
01:19:26.640 --> 01:19:29.600
There is a subexponential
algorithm for this problem.
01:19:29.600 --> 01:19:33.250
But it's still up in the air.
01:19:33.250 --> 01:19:35.250
A lot of people like to
assume that this is true
01:19:35.250 --> 01:19:39.450
because it makes life
a lot more beautiful,
01:19:39.450 --> 01:19:41.890
especially from an
inapproximability standpoint.
01:19:41.890 --> 01:19:45.980
So for example, Max 2SAT, the
best approximation algorithm is
01:19:45.980 --> 01:19:47.581
0.940.
01:19:47.581 --> 01:19:49.080
If you assume that
unique games, you
01:19:49.080 --> 01:19:50.860
can prove a matching
lower bound.
01:19:50.860 --> 01:19:54.270
That was Max 2SAT for
Max Cut, as was mentioned,
01:19:54.270 --> 01:19:59.490
0.878 is the best upper
bound by Goemans Williamson.
01:19:59.490 --> 01:20:01.720
If you assume unique games,
then that's also tight.
01:20:01.720 --> 01:20:04.415
There's a matching
this minus epsilon
01:20:04.415 --> 01:20:09.830
or plus epsilon
inapproximability result.
01:20:09.830 --> 01:20:12.560
And vertex cover, two.
01:20:12.560 --> 01:20:14.290
You probably know how to do two.
01:20:14.290 --> 01:20:17.560
If you assume unique games,
two is the right answer.
01:20:17.560 --> 01:20:19.400
If you don't assume
anything, the best
01:20:19.400 --> 01:20:21.850
we know how to prove
using all of this stuff
01:20:21.850 --> 01:20:27.900
is 0.857 versus 0.5.
01:20:27.900 --> 01:20:32.950
So it's nice to assume
unique games is true.
01:20:32.950 --> 01:20:36.620
Very cool results is if you look
at over all the different CSP
01:20:36.620 --> 01:20:39.530
problems that we've seen,
all the Max CSP problems,
01:20:39.530 --> 01:20:41.900
and you try to solve it
using a particular kind
01:20:41.900 --> 01:20:46.990
of semi-definite programming,
there's an SDP relaxation.
01:20:46.990 --> 01:20:49.540
If you don't know SDPs,
ignore this sentence.
01:20:49.540 --> 01:20:52.440
There's an SDP relaxation
of all CSP problems.
01:20:52.440 --> 01:20:54.810
You do the obvious thing.
01:20:54.810 --> 01:20:57.740
And that SDP will have
an integrality gap.
01:20:57.740 --> 01:21:00.370
And if you believe
unique games conjecture,
01:21:00.370 --> 01:21:04.170
then that integrality gap equals
the approximability factor,
01:21:04.170 --> 01:21:04.900
one for one.
01:21:04.900 --> 01:21:07.280
And so in this sense, if
you're trying to solve any CSP
01:21:07.280 --> 01:21:09.310
problem, semi-definite
programming
01:21:09.310 --> 01:21:13.550
is the ultimate tool for all
approximation algorithms.
01:21:13.550 --> 01:21:16.000
Because if there's
a gap in the SDP,
01:21:16.000 --> 01:21:17.730
you can prove an
inapproximability result
01:21:17.730 --> 01:21:19.770
of that minus epsilon.
01:21:19.770 --> 01:21:21.182
So this is amazingly powerful.
01:21:21.182 --> 01:21:23.390
The only catch is, we don't
know whether unique games
01:21:23.390 --> 01:21:24.850
conjecture is true.
01:21:24.850 --> 01:21:27.580
And for that reason, I'm not
going to spend more time on it.
01:21:27.580 --> 01:21:32.680
But this gives you a flavor of
this side of the field, the gap
01:21:32.680 --> 01:21:36.590
preservation approximation.
01:21:36.590 --> 01:21:38.784
Any final questions?
01:21:38.784 --> 01:21:39.748
Yeah.
01:21:39.748 --> 01:21:41.658
AUDIENCE: If there's a
subexponential-time algorithm,
01:21:41.658 --> 01:21:46.050
is it still OK for
it to be NP-hard?
01:21:46.050 --> 01:21:49.030
PROFESSOR: It's
fine for a problem
01:21:49.030 --> 01:21:52.070
to be slightly subexponential.
01:21:52.070 --> 01:21:56.470
It's like 2 to the n to
the epsilon or something.
01:21:56.470 --> 01:21:59.100
So when you do an
NP reduction, you
01:21:59.100 --> 01:22:00.880
can blow things up by
a polynomial factor.
01:22:00.880 --> 01:22:04.500
And so that n to the
epsilon becomes n again.
01:22:04.500 --> 01:22:06.390
So if you start
from 3SAT where we
01:22:06.390 --> 01:22:10.100
don't believe there's a
subexponential thing, when you
01:22:10.100 --> 01:22:13.410
reduce to this, you
might end up putting it--
01:22:13.410 --> 01:22:15.370
you lose that polynomial factor.
01:22:15.370 --> 01:22:18.989
And so it's not a contradiction.
01:22:18.989 --> 01:22:19.530
A bit subtle.
01:22:19.530 --> 01:22:22.340
01:22:22.340 --> 01:22:23.120
Cool.
01:22:23.120 --> 01:22:25.410
See you Thursday.