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

25.5 P=NP Recap
- NP, NP-Hard, and NP-Complete
- Proving a problem is NP-Hard
- Proving P=NP
- Elvis has left the building!

David Evans and Nathan Brunelle
University of Virginia
---

To recap, we've got these two ways of
thinking about problems.

We've got functions that are in this
complexity class NP, which stands for.

Non-Deterministic Polynomial Time,
that we can solve it with a

non-deterministic Turing machine in a
polynomial number of steps in terms of the

size of the input, and the other way to
define that class is there is some

certificate, or we also call
that a witness, that you can

verify one output to that
function in polynomial time.

If the output is one,
there's some way to prove

it that you can verify
in polynomial time.

Like, give me the actual path.

A function is NP-hard if every function
within NP can be reduced to it.

That means it's at least as hard as the
hardest problem within NP.

And if it's also within class NP,
then we call it NP-complete.

What the Cook-Levin theorem proved,
and we've seen what they actually proved

was a little different, but the way we
like to state it now and the way the book

states it, is that we have
a problem, 3SAT, which

is the satisfiability of
Boolean formulas in CNF.

There's nothing really special about the
3SAT, it's just that's a simple way to

write down the Boolean formulas that
allows it to prove it.

So we could do satisfiability
of any formula, but what we

know is that that satisfiability
problem is NP-complete.

If we want to prove some function G is
NP-hard, what do we have to do?

So what it means to be
NP-hard is that there is a

polynomial time reduction
from every problem in NP to G.

So we could try to
prove that, which is what

we did for one problem,
the NANSAT problem.

We proved that there's some way,
because of the definition of NP and what a

verifier is, and that it runs in polynomial
time, that every problem reduces to it.

The other way to do it is, well now,
once we know some problem that's NP-hard,

we only have to show one reduction.

We have to show that this problem that we're
trying to show is NP-hard reduces to it.

So that's almost always going to be the
way we do it now.

Take advantage of the problems that we
already know.

And as you learn about more
problems that are NP-hard,

you have more and more
options for how to do this proof.

And there are lots and lots of them.

So this is just a small
subgraph of all the reduction

proofs that have been done
to show problems are NP-hard.

Satisfiability is the one that's in the
middle here.

If we want to prove a problem is
NP-complete, we've got to do two things.

We've got to show that it's within class
NP.

That's an element of.

And we've got to show that it is NP-hard.

What do we have to do to prove P equals
NP?

Well, that means those sets are equal.

For every problem that is in NP,
and maybe we can do this from the

definition, but the more
likely way is, well, we know

every problem in NP maps to
some problem that's in NP-hard.

Any problem in NP-hard,
if we can map any problem

that's NP-hard to P, then
we know they're equal.

So all we've got to do is find one problem
that's in NP-hard that can be polynomially

time reduced to one problem that's in P.
And then we prove they're equal.

That sounds easier than it is, because
no one actually has been able to do that.

But that would be a proof if we could do
it.

There could be other ways.

Okay, so when we don't have a proof,
we can do surveys.

At least people have done surveys of pools
of computer scientists, and it turns out

that the number that
think P is not equal to.

NP, according to the
surveys, is about 88%.

Very scientific survey of people who
happen to be on a mailing list,

and were willing to respond.

You can see all of these other answers
that were, well, maybe it depends on some

choice of axioms that we use in arithmetic
that we don't all agree on.

Maybe we don't care.

That number has gone to zero, but
according to the survey, it went to zero

because they changed
the survey, so you

couldn't answer anything
other than yes or no.

The quote is, of course, P is not equal to
NP.

Anyone who thinks they're equal is,
like, thinking Elvis is alive.

And the response to
that is, Elvis definitely

is alive, and he's
working on P equals NP.

And I don't know if that's true or not.