---
Video Title: Questions about P and EXP
Description: Theory of Computation
https://uvatoc.github.io/week11

24.1 Questions about P and EXP
- Recap: Complexity Classes P and EXP
- Three Questions

Nathan Brunelle and David Evans
University of Virginia
---

What we're going to do
today is continue with what.

Professor Brunel foreshadowed
at the end of the last class.

So we're getting into what most people,
and I would agree with, think is the

deepest question in all of computer
science.

Arguably the deepest question in all of
mathematics.

That is an open problem that is something
that you should all understand well.

Probably won't all
solve it because it's an

open problem and no
one has solved it yet.

But you should at least
understand what the problem is,

why it matters, what the
implications of solving it are.

And you've probably heard this at the end
of the last class, but you've probably

heard it in lots of other places talked
about as this p equals np question.

Or p versus np, which is kind of a mis-way
of stating it.

But that's where we're going to get to
both understanding what the problem is and

what it would mean to solve it and what
the implications of that would be.

Let's recap where we got last week.

So we looked at problems.

These were the four main ones.

Two of these problems seem to be easy.

Easy meaning we can
find fast algorithms that

solve them using our
standard notion of computing.

Whether that's a Turing machine or any of
these classical models.

And then we had these other problems which
are kind of similar.

3SAT is like 2SAT, but now
instead of being limited to two

terms and a clause, we can
have three terms and a clause.

Now it looks like the problem's a lot
harder.

It seems like the best
way we'd know it, and

this doesn't mean
it's the best algorithm.

It's just the best
algorithms that we know of

solving both the longest
path and the 3SAT problem.

They seem to basically require searching
the space.

Searching the space of possibilities.

All is in quotes, because certainly we can
do some things to cut off that search.

We don't have to try every single
possibility.

Some of them we can, in a large group, say
we know this is not a good direction to go.

But we essentially have to search the
possibilities.

We don't know any way
to get to a solution without

doing this huge search
of an exponential space.

All of these are problems
where, with enough time

and space, we have an
algorithm that can solve them.

What we don't know is whether there's an
efficient algorithm to solve it.

And what we defined was this
complexity class that captures

this whole space of all the
problems that seem to be easy.

And our notion of easy is there is a
polynomial time algorithm.

If that exponent on C is high enough,
we could have big O around that,

but by increasing C, we don't actually
need that.

Since C can be any natural number here,
this class is problems that a Turing

machine can do in some polynomial number
of steps.

And the big union is unioning it of all of
the exponents.

Any natural number can be the power.

So certainly if C is high enough,
that might still be impractical.

If we're talking about doing something on
a graph the size of the internet,

even if C is above 2, it starts to become
impractical.

Even doing things that are quadratic,
scaling to the billions is too expensive.

One of the reasons that this notion of
polynomial time seems satisfying is,

at least over the history of
the last 300 or 400 years of

computing, computing power
seems to increase exponentially.

Every 15 years, we have about double the
computing power we had.

So as long as that's the
case, eventually that's

going to catch up to any
polynomial time algorithm.

And these other ones, well, they seem to
be hard.

But we don't know if they're hard.

We know that if we have exponential
resources...

Exponential here is in the size of the
input.

And that basically means we can try all
possible combinations.

If we can try all possible
combinations, we can solve these

problems that seem to be hard
in a very straightforward way.

We just try all possibilities until we
find one that works.

Or if none of them work, we give up.

For 3SAT, trying all
possibilities just meant

for each variable, it has
one of two assignments.

And we can try all combinations of
assigning values to variables.

There's an exponential number in the
number of variables possibilities to try.

If there is a satisfying assignment,
one of those is going to be it.

We're going to find it.

Longest path.

We're looking at the longest path between
two matrices that doesn't repeat a node.

We can try all possible paths.

All possible symbol paths.

And the number of possible paths is
exponential in the number of nodes.

So we can do that search.

Let's make sure that everyone understands.

So we have three review questions.

We'll go through each of these,
but I want you to think about them first.

So the first review question, is P a
proper subset?

So that means there has to
be at least one problem that

we know is in EXP that's
not in P for this to be true.

So the second question is longest path in
EXP.

Everyone should get that one correct.

And then the third one is longest path
within class P. Thank you.

Take a deep breath.

Stay happy.

Thank you.