---
Video Title: The P=NP Question
Description: Theory of Computation
https://uvatoc.github.io/week11

25.2 The P=NP Question
- Is Omniscience Empowering?
- Possible answers to P = NP?
- Polynomial-Time Reductions between Problems in P
- Consequences of P = NP

David Evans and Nathan Brunelle
University of Virginia
---

Now we've defined these classes, it
seems like they should be very different.

Our class NP, we're adding all
this power, which we can think

of as always guessing correct,
or always doubling our machine.

And the question is, are there functions
that we can compute with the polynomial

number of depths, where adding all that
power changes what we can do?

And this is the question we don't know the
answer to.

I'm drawing these classes now,
making them look different.

So we've got the yellow circle is P,
the purple circle is class NP.

All of the ones that are
in NP here, they could

be NP, but we don't
know if they are or not.

We don't know that they're not NP.

We do know that they are within the class
NP.

And we know that because we can show that
there is either a non-deterministic Turing

machine that solves them, or a polynomial
time witness.

If the classes are
equal, if these sets are

equal, that means every
function in NP is also NP.

One way to prove that
would be, go through all the

functions that are in NP
and prove each one is NP.

There are infinitely many, we are not
going to finish that process.

So definitely that's not a strategy that's
going to lead to our proof.

What we're starting to get to,
so you've seen ways to do reductions.

If you knew how to solve long path,
you could also solve 3SAT.

There's a way to use long path to solve
3SAT.

So this meant that we can map this problem
to the other one.

If we knew long path also reduced to a
problem NP, that would cover 3SAT as well.

So if we can show
reductions between problems,

we're going to only need
to show it for one problem.

Once we've shown these problems are
equivalent, then if we can show that one

of the problems that's equivalent is also
NP, then we're done.

And the big theorem that we're
getting to is showing that all

of the problems that are in NP,
they can be reduced to 3SAT.

Every problem in class NP can be reduced
to 3SAT.

And that means they could also all be
reduced to longest path.

Once they're all reduced to 3SAT,
then if we can reduce 3SAT to any problem

in P, well that would show all these
problems can be reduced to each other.

That they're all within class P. If we can
prove that we can't, if we can get a

separation and know that there's no
problem in P that it can be reduced to,

well that would mean that the classes are
different.

That would explicitly be an example of
here's a function in NP that's not in P.

So that's what we want to get to.

Certainly if we had to
prove for every single

problem, we're never
going to get there.

These problems seem that there's not going
to be any efficient way to solve them,

and people have been trying for a long
time without success.

But people have also been trying for a
long time without success to separate them.

So kind of the trying
for a long time without

success argument does
not hold up very well.

The theorem that we're gonna get to is to
say that we've got one problem,

which is the 3SAT problem, that every
problem that's within class NP,

so this is our big class
NP, there is a polynomial

time reduction from every
problem within NP to 3SAT.

We don't need to know anything about the
problem, other than that it is within

class NP, and we can guarantee that there
is some reduction.

We don't necessarily know exactly what the
reduction is, but there must exist one.

Once we've got one problem that we said
every single problem within this

infinitely large class NP can be reduced
to this problem in polynomial time,

whatever we can show about this problem,
if this is within class P, then all of

these other problems transitively can also
be solved in polynomial time.

The reason we use this less than or equal
to symbol for reductions is to get across,

yes, it is transitive, just like less than
or equal to.

It also should give you the intuition of,
it's about hardness.

This is harder, or at least as hard.

I don't know if you learned
about the alligator mouth

wants to eat the bigger
number when you went to school.

I learned about that.

Here the alligator mouth wants to eat the
harder problem.

So this means 3SAT is at least as hard as
every problem within NP.

Where we're talking about polynomial time
reductions, right?

So at least as hard is modulo what
polynomial work.

If it could be reduced to a
polynomial time problem,

so could every other
problem within class NP.

Why do they have this transitive property?

Why can't we keep doing them?

How do we know there's a polynomial time
reduction between X and Z?

Good.

Yeah.

So what happens when you add two
polynomials?

You get a polynomial.

So the work here to go from X to Z,
if you have to go through these two steps,

is this work plus this work.

And if we add polynomials, whatever
polynomials they are, and these can be

totally different polynomials, they're all
polynomial in N, the size of the problem.

Let's be careful.

This is polynomial in the size of that
problem.

Is this polynomial in the same N?

What's the biggest size the Y problem
could have for the second reduction?

It's got to be polynomial in that.

We can increase the
size of the problem as we

do a reduction, but only
by a polynomial amount.

We're still going to be a polynomial.

If we're talking about the actual number of
steps to solve it, that's going to be more.

Doing two reductions is going to be more
than doing one.

There might be a more clever one that
composes them.

But they're all still going to be
polynomials.

And that's all we care about, at least in
defining these classes.

That's our definition.

Polynomial time reductions just mean there
is some function that is in p.

So p is things that we can
do in polynomial time, such

that we can transform
the input that we had for f.

So we're trying to show that
we can solve x using g, that we

can get the right output for
f of x by running g on r of x.

That means that whatever time it takes to
run g, we can solve x in the time it takes

to run g plus some amount of time that it
takes to run r, which is a polynomial in

this case, because we limited r to things
that we can do in polynomial time.

We've got two possible answers to this
question.

Either the sets are equal, or there
are some things in NP that are not in P.

They can't be disjoint, because we know
that NP definitely includes everything in P,

and it can't be that P is more powerful.

If this is the case, what
polynomial reductions

are there between the
problems in that circle?

In order for there to be a polynomial time
reduction, there has to be some function

that is in polynomial time that we can run
on x, and then we can run g on the output

of that function and get the result of f
of x.

So if we have two functions that are in
polynomial time, let's say f is in P and g

is in P. Can we pick
something for r that's almost

certainly going to work
with a little bit of a tweak?

R could be f.

They're in polynomial time, f is a
perfectly good choice for r.

Is this going to work?

What's the output of r of x going to be
then?

It's going to be f of x.

The result we want is f of x.

But g is going to run on that output.

So what do we need to replace the output
with?

Yeah.

So what we're going to do for r instead of
f, we're going to do r is if f of x,

what should the output of r of x be if f
of x equals 1?

Well, here we've got to know
something about g. We've

got to find some input to g
where the output of g is 1.

So the only thing we've got to know about
g is there's some input to g.

It can be any input that g produces a 1
on.

So otherwise, it should be some input that
g of y 0 star.

So as long as we know some
input that g outputs a 1 on and

some input that it outputs a
0 on, we have this reduction.

So between any two polynomial time functions,
we should be able to find a reduction.

There's only one little problem case.

When does this not work?

Yeah.

If g is a constant function, we're stuck.

We can't find any input where it outputs 1
if g always outputs 0.

So there are two functions that we can't
find reductions for.

But those are kind of trivial.

So for any interesting function,
we can always find the reductions.

So if p equals np, there
would be reductions

between all of these
problems in all directions.

The trivial reductions would work because
you could just run the original problem in

polynomial time, and then you'd have to
know an input.

But for all of these problems,
we know them enough to know an input.

What if P is not equal to NP, meaning it
must be a strict subset.

We still have these reductions.

We could have reductions between these and
we saw one, but we know there are not

reductions between these, between ones
from NP to P. There must be some problem

in NP that does not reduce to a problem in
P. Otherwise, they would all be the same.