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

24.2 Introducing NP
- Is LongestPath in P?
- Is LongestPath in EXP?
- Making LongestPath a Decision Problem
- Find the Longest Path (song by Daniel J. Barrett)
- Introducing class NP

The "Find the Longest Path" song is from http://www.jakubw.pl/inne/longest.html (and video from https://www.youtube.com/watch?v=a3ww0gwEszo).

The people in the Longest Path song video (all of whom have made substantial contributions to theory of computation) are, in order of appearance: Shafi Goldwasser, Virginia Vassilevska Williams, Julia Chuzhoy, Sofya Raskhodnikova, and Barna Saha.

David Evans and Nathan Brunelle
University of Virginia
---

Before we get to the proper subset, is
it obvious that it's a subset or equal to?

Good.

Yeah.

We know that this is true.

Because if we have more time, what time
means is the set of functions a Turing

machine exists that can compute those
functions within that number of steps or fewer.

So if we increase the
number of steps, we can

always do all the
functions we could before.

2 to the end of C is greater than n to the
C.

It's definitely true once C is greater
than 2.

To show the additional property that it's
a proper subset, what do we need to do?

Good.

Yeah.

We need to know there's some function in
EXP.

It's not in P. Do we know any functions
that would work for our choice of F here?

Yeah.

Longest path?

Longest path.

Good possibility.

So what will we have to know to know that
the longest path works for this?

We know the longest path is definitely
EXP.

Do we know that it's not in P?

If you knew that, you would all have A
pluses in the class.

It's not known whether it's in P or not.

So that's not going to work.

So maybe they're the same.

At least the one problem that we think we
know is hard.

Well, two problems.

We know 3SAT.

We know the longest path.

We can think of some other problems that
are hard.

But we don't know for
sure that it's not in P.

To know that something
can't be done is hard.

To know that it's not in
P, we'd have to know there

is no polynomial time
algorithm that can solve it.

We don't know of one.

And we know that no one else knows of one
either.

Or if they know of
one, they're keeping it

very secret for some
national security reasons.

But as far as we know, no one knows of
one.

But that doesn't mean it doesn't exist.

We just haven't found it yet, maybe.

We'd have to prove that that function
cannot be done with any polynomial time.

Turing machine to know that it's not in P.
So is there some other function we could

use for this that would separate these
classes?

What's an example of a function that we
know is not in EXP?

Do we know any functions not in EXP?

Yeah.

Yeah, good.

All of our undecidable problems,
these are uncomputable functions.

So forget whether we're limited to an
exponential number of steps.

We can't solve these with no limit.

We know that there's no algorithm that
solves it.

That for any finite number of steps is
guaranteed finish.

So we know halts is not in EXP.

Can we make a version of halts that will
be in EXP?

Yeah, sure.

Halts is defined as it's eventually going
to stop forever.

Well, we can modify halts, create a new
function that is going to be...

That's a long name for it.

It takes as input a Turing machine.

And it outputs true if that machine would
halt within 2 to the end of the 100 steps,

where now n is still the length of the
input.

So now that input is the Turing machine.

This is a very well-defined function.

How can we solve that within time EXP?

Sure.

We simulate the
machine described by the

input for up to 2 to the
end of the 100 steps.

And if it still hasn't halted,
we output 0.

So this is within EXP.

Do we know if that's in P?

Yeah.

Well, for that to be in P, we'd have to
simulate every possible Turing machine

faster than it can actually run.

To simulate 2 to the
end of the 100 steps in

something that is only
scale as n to the C...

Well, that's a smaller number of steps.

So we've got to simulate the Turing
machine in less steps than it is.

Is that possible?

For some machines, it might be.

But it better not be possible for all
machines.

If we could do that for all machines,
then the machine that we're using to

simulate them, we should simulate that
one.

And we can simulate that one in fewer
steps than it took before.

And then we can simulate that one in fewer
steps.

Eventually, every machine runs in no
steps.

Something's really wrong
if we can simulate every

machine in fewer steps
than it actually takes.

So we know that that is not in P. This is
maybe not a super-interesting function.

It's not something well-defined like
longest path.

But it's one that we can clearly
say is definitely within class.

EXP and not within P. So we
know those classes are separate.

And that's all we need to know that this
is true.

We've separated two really big complexity
classes, right?

So I sort of told you the longest path is
an EXP.

Was that actually correct?

We should look a little
more carefully how EXP

is defined before we
assume this is correct.

Here's our definition of EXP.

This definition defines both P and EXP.

And they're defined very precisely.

It is a set of functions.

And it is a set of functions from 0,
1 star to 0, 1.

So the output is just 1, 0 or 1.

And to be in EXP, there's some polynomial
such that there's a machine that computes

that function in fewer than 2 to the P
length of input steps.

For this precise definition of EXP is
longest path within EXP.

So what's the output of longest path?

Yeah.

Well, we kind of have a type mismatch.

So the output of longest path,
this is some natural number.

It's a length.

It's not just 0 or 1.

Definitely there can be longer paths than
0 or 1.

And in order to be in
EXP the way this was

defined, its output should
only be either a 0 or 1.

So this is saying we're only talking about
decision problems.

We're talking about functions that only
output 0 or 1.

So does it make sense to talk about
longest path in EXP?

It's not the way that we define longest
path here.

Can we fix that?

Good.

Yeah.

So we're going to add a number.

We're going to add a number.

So we're going to turn it into a decision
problem.

What we're going to do, we're adding a
path length.

And now what the output means is whether
or not there is a path of that length.

The output is 0 if there's no path of that
length.

The output is 1 if there is a path of at
least that length.

So that length or longer.

So now we have a decision problem.

We've added one input.

It's an input that is not as hard to find
as the actual path.

If what we have is a Turing machine that
solves longest path decision in polynomial

time, can we solve longest path in
polynomial time?

So our goal now... and we can write this
instead of as a Turing machine,

because I don't have enough room on the
slide.

Our goal is to implement longest path.

And we already have an implementation of
longest path decision.

Someone has given
us an implementation of

this function that does
the decision problem.

Is there a way that we can now solve
longest path?

Yeah, we can start at zero.

How high do we need to go up?

The number of vertices.

Yeah, it's a simple path.

The longest possible answer is the number
of vertices.

So we're going to go
from zero to... this is

not Python code... up
to the length of vertices.

And then we're going to try passing in the
graph... S, T, and N.

And what should we do now?

What we actually want to do... we want a
knot here.

We're going to keep going until that is
false.

If that returns zero, that means there is
no path of that length or more.

And then whichever the last one it was,
was the longest.

So we're going to return... we could
return N minus one.

So is this polynomial time?

So we're assuming this is in polynomial
time.

To be within polynomial time, if the
number of times we're calling it,

is a polynomial.

We're still in polynomial time.

So we're going through this loop up to the
number of vertices time.

Remember, we're always talking about with
respect to the size of the input.

So how does the number of vertices relate
to the size of the input?

Well, we'd have to think a little bit
about how to encode it.

If the graph was encoded
as just a number, the value

of a number can be
exponential in terms of their size.

Encoding the graph, we need to encode the
edges.

But we didn't say anything about the
number of edges here.

So each edge requires some log of the
number of vertices.

If we're going to encode
two vertices, we could

identify them with the log
of the number of vertices.

Or we could encode the graph as an
adjacency matrix.

So if this is the graph, we're going to put
ones in the places where there are edges.

Between the two nodes, right?

So that's going to be an input size that
is the length of v squared.

Is what we need to encode the graph.

So is the number of iterations polynomial
or exponential in the size of the input?

We should be a little worried.

It might be exponential.

Because this is the value.

This is not the length of v.

This is the magnitude of v.

Going through the number of vertices.

Can we solve this problem
and be more convinced

this is going to be
in polynomial time?

Is there a more efficient way to search
for the right value of n?

We don't have to actually loop through a
one by one.

So if we're searching for n, we can do a
binary search.

We can do a binary search.

If we do a binary search, then we're going
to be in log of v iterations.

And that's definitely a polynomial in the
size of the input.

The size of the input is, if it's this
adjacency matrix, it's log of v squared.

And we're doing log of v iterations.

This means that if we have a polynomial of
time solution to longest path decision,

we can use it to get a polynomial of time
solution to longest path.

Any problem that is to find an input like
this, that we can break down this way,

we can always convert to a decision
problem.

You should think carefully about,
if something is framed as a problem that's

not a decision problem, what the
equivalent decision problem will be.

Because all of these complexity classes
are really defined for decision problems.

So now we get to the tougher question,
which we've kind of alluded to.

Whether longest path is in P, right?

So we know it's within EXP.

And I'm going to use longest path now to
mean the longest path decision problem.

This is such a tough question,
we need to listen to a song.

Oh, find the longest path.

If you said P is NP tonight, there would
still be papers left to write.

I have a weakness.

I'm addicted to completeness.

And I keep searching for the longest path.

The algorithm I would like to see is a
polynomial degree.

But it's elusive.

Nobody has found conclusive evidence that
we can find the longest path.

I have been hard working for so long.

I swear it's right and he marks it wrong.

Somehow I'll feel sorry when it's done.

GPA 2.1 is more than I hope for.

Gary Johnson, Karp, and other men and
women.

Try to make it order and log in.

Am I a mad fool if I spend my life in grad
school?

Forever following the longest path.

Whoa, just find the longest path.

Whoa, just find the longest path.

Whoa, just find the longest path.

So hopefully that helped.

You've had some insight and inspiration
now.

But we don't know the answer.

So we have this open question.

We don't know whether it's in P or not.

We know it's in EXP.

What we're going to get to now is...

Well, there is a class that we know that
it's in.

That's a very interesting class.

Which is this class that is called NP.

Right away, do we know something about the
relationship between NP and EXP?

Even without telling you what NP is?

Since we already said we know there are
problems that are in EXP that are not in.

P. And we know that longest path is in P.
If we didn't already know it was a proper

subset of EXP, well, we would know
something else.

It would cause other problems.

So we do know that it's a proper subset of
EXP.

Ohhhh... Ohhhh...
Ohhhh... Ohhhh... Ohhhh...