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

24.3 Complexity Class NP
- Informal Notion of Class NP
- Nondeterministic Machines
- "Power" of Machines
- (review) NFAs are equivalent in power to DFAs
- Are things different for TMs? (answered in next segment)

Nathan Brunelle and David Evans
University of Virginia
---

So what the class NP
is, and we're going to

start with two informal
definitions of it.

The one that the book focuses mostly on is
the second one.

They kind of mention that the name NP
comes for historical reasons and really

focus on this definition and define this
precisely.

This is the class of problems that we know
that we can verify a solution.

If we're given a witness, we can verify in
polynomial time that it's correct.

The place the name NP comes from,
and I think a useful intuition for

understanding what the class NP is,
is non-deterministic Turing machine.

So the N here does not stand for non.

It stands for non-deterministic.

So the class NP is the class of
functions that can be computed

in polynomial time using a
non-deterministic Turing machine.

And what we don't know is
whether a non-deterministic.

Turing machine is more
powerful than a standard one.

Before getting to
non-deterministic Turing machines,

I want to review
non-deterministic finite automata.

Let's start with deterministic finite
automata.

They are machines where, at every step,
you know exactly what to do.

You have a rule.

You look it up.

There's no uncertainty.

You do what that rule says.

And there is only one choice at every
step.

That's what it means to be deterministic.

For whatever state you're in, and that
means the entire configuration,

you know exactly what's going to happen
next.

So that's deterministic.

What non-deterministic means is we can now
have rules that give us options.

In the same state, on the same input,
we can do two different things.

In state two, if we saw a zero or a one,
we go to state one.

Now we can add a rule that says,
well, we could also stay in state two.

So we have two possible
things to do on the exact

same input, starting in the
exact same configuration.

That's what it means to be
non-deterministic.

Once we allow that, that means,
well, one way to think about that is when

we're executing, now we're in state two,
we read a one.

Now we could be in two possible states.

We could be in state one, or we could stay
in state two.

And now, the next input, let's say,
it's another one.

Well, if we're in state one and we read a
one, we stay in state one.

If we're in state two and we read a one, we
can do either of those two possible things.

In this case, these are the same states,
so we can merge those again.

Those are indistinguishable once we've got
there.

Here's a non-determinist finite automaton.

How do you know that
it's non-deterministic, other

than that it says that
on the top of the slide?

Good.

Yeah, it's got two different things you
can do on node one on a zero.

You can either stay in one, or you can go
to state two.

We have one accept state.

We only accept in state three.

So what does this machine do?

Should that accept?

The intuition of what it means to execute
is if your goal is to accept, every time

you have a choice, you make the right
choice.

So if there's some way of making the
choices when you have a choice what to do

that leads you to an accept state,
then you should accept.

If there's no way to make the right
choices, then you should reject.

So any string that ends in zero one,
we should accept.

If our last two are zero, one,
the way we process with a finite state

machine, we can't just jump to the last
two.

We don't know the end of the string until
we get to it.

Because of this
non-determinism property, we can

just stay in state one
as long as we need to.

If the last two bits in the input string
are zero, one, we will accept.

And because the non-determinism
makes the right choices at

every step, we don't have to
do anything to think about that.

We just know that it's
going to follow that path

and find the path that
gets to the accept state.

We can think of our execution model in two
ways.

So we can think of it as being
all-powerful.

That every time it has to face a choice,
we can split into two machines.

One that makes each choice.

And we can keep all these machines that we
need.

Every time we make a choice, we have
infinite power.

We just make new machines that follow both
choices.

And if any of those machines that we
create in our execution accept, we accept.

If some of them blow up or get stuck or do
something else, that's okay.

If any one of our potentially
infinitely many machines,

it's not going to actually be
infinite, accepts, we're done.

The other way to think about it is the way
I describe first.

Is that every time we have to make a
choice, we magically guess the right choice.

Based on all the input that we haven't
even seen yet, we magically somehow know

how to make the right choice that's going
to lead to the accept state.

Even though we haven't seen the rest of
the input yet.

Both of those sound like pretty amazing
superpowers.

We certainly cannot build physical machines
that do this, do either of these things.

For finite state machines, does this add
power?

One of those two ways, whichever one
sounds more powerful to you.

Does that make a
finite state machine more

powerful, once we
add that capability to it?

How do we answer these kinds of questions?

If we want to talk about whether one type
of machine is more powerful than another,

our definition of the power of a machine
is the functions that it can compute.

In order to say if type A is
more powerful than type B, we've

got to understand the set of
functions that they can compute.

If they're like this, they're disjoint.

Maybe A can compute
some things B can't compute,

B can compute some
things A can't compute.

Neither one is more powerful.

But most of the things we've looked at
have been either like this.

One is more powerful than the other.

Functions that B can
compute would be a strict

subset of the functions
that A can compute.

If you were thinking about
non-deterministic finite state machines

and deterministic finite state machines,
which would be A and which would be B?

Which one is potentially seems like it's
more powerful?

Yeah, so the non-deterministic is adding
power.

Every deterministic state machine can be
interpreted as a non-deterministic one.

It's just one that there's never any
choices.

So certainly the only thing we are doing
is potentially adding power.

We're not losing power.

But it could be Could be that every
function that we can compute with a

non-deterministic finite
state machine, there is some

equivalent deterministic
machine that can compute it.

And if we're going to
show this, well, we've

got to show how we can
construct that machine.

If we can show that we can always
construct a deterministic machine for any

non-deterministic finite state machine,
that would show their equivalent.

To show their equivalent, we would need
two things.

First, is there any function
that the deterministic machine

can do that the non-deterministic
machine cannot do?

No.

We're only adding capability.

That capability may help us or may not,
but it definitely doesn't make it worse.

And the proof is that every DFA can be
simulated by an NFA because it is already.

So this one is harder.

Is there anything that we can do with an
NFA that we can't do with a DFA?

Certainly, we don't
want to go through all the

functions because
there are infinitely many.

So let's try to think of it as a
construction.

Remember what the F stands for.

The number of states is finite.

So if we're simulating our omnipotent
machine where every time we have a

decision we can split,
is there a way we can

simulate that with a
finite state machine?

The regular finite state machine is in one
of the three states.

How many different
configurations can the

non-deterministic
three-state machine be in?

The number of states is finite.

If we're simulating
the non-deterministic

machine, we are in some
subset of those states.

So we can create a machine
where each state now

represents a subset of the
states in the original machine.

And it's going to be
deterministic and can compute

the same function as the
non-deterministic machine.

All we've got to do is just keep track of
the possible subset of states.

So all we need to do is now create a bunch
of states.

For any finite state machine, we can do
this.

How many states are we going to have?

In the worst case, how many
states do we need to convert

the non-deterministic
machine to the deterministic?

Yeah.

Yeah.

It's the power set.

We need one state to represent every
subset.

Some of them may never be used.

And pretty much right away, we know we're
never in the empty set.

Because if we're in the empty set,
we have already failed.

We're never going to accept that.

We start in the state that is the subset
of states, just state one.

Right?

That's the equivalent of this arrow.

Now we see a zero.

We go to the state that is composed of
these two states.

Where we go on a one is we stay here.

In state one, two, when we see a zero,
we're going to go...

State two doesn't go anywhere on a zero,
so we're going to go back to state one.

In state one, two, if we see a one, we're
going to go to state three and state one.

What we do on zero and one
is based on all the states that we

could reach from that input
starting from that set of states.

So we can do this construction
mechanically.

Which are the accepting states in our
purple deterministic machine?

Good.

Any state that includes
an accepting state, which

in this case, any state
that includes three.

So this is accepting, this is accepting,
this is accepting, and this is accepting.

We can mechanically
convert any non-deterministic

finite state machine
into a deterministic one.

So it is not more powerful.

Every function that we can compute,
we added this magic power of

non-determinism, and it didn't even help
us.

Did it help us?

Yeah.

So it didn't help us as far as power.

We can compute exactly the same set of
functions we can compute before.

It helped us in terms of what we can
compute with a certain number of states.

So if we had separate function classes
for, and we certainly can define that,

the set of function that you can compute
with a non-deterministic finite state

machine with three states is a bigger set
than the set of functions you can compute

with a deterministic machine with three
states.

Did it help us on time?

How do you count time for a finite
automaton?

Pretty much every input symbol is one
step.

We don't go back on the input.

The time it takes to execute is the same.

Now, to actually
simulate the execution with

a real physical machine
might be different.

If you are doing network scanning with
regular inspections, which are easily

turned into non-disturbishing finite
automaton, if you want to do it really

fast on flying speeds in your router,
you want to convert those to deterministic

machines that you can evaluate more
quickly.

But in terms of our theoretical model,
it's one step for each symbol in the input.

That was for finite state machines.

Now we're asking the same question for
Turing machines.

Why was this easy for finite state
machines?

To see that non-determinism didn't help?

Yeah, the total number of configurations
is finite.

Having non-determinism blows up the number
of configurations, because now it's the

power set of the number of states instead
of the number of states we started with.

But it's still finite.

What happens with Turing machines?

Can we think of what it means to add
non-determinism to a Turing machine?

So the states of the Turing machine are
still finite.

The internal states we
can keep track of now, that's

going to scale to the power
set of the number of states.

But what else do we have to do?

Every time we have a choice.

Yeah.

Every time we have a choice.

If our notion of what it means
for a non-determinism machine

to execute is every time we
have a choice, we try both.

Well, the only way to
do that with a Turing

machine, the tape is
part of the configuration.

So we've got to copy the tape.

Every time we have
a choice, we've got to

make two configurations
that are full copies.

So we're going to have to copy the tape.

And every time we make a new choice,
we've got a new tape.

Oh, and how long is the tape?

Infinitely long.

The other thing is, well, we don't know
how many steps it takes.

So a finite state machine,
we know it executes

for the length of the
input number of steps.

How many steps can a Turing machine
execute for?

Yeah.

Well, they can run forever.

That's why we have halts.

So we don't have a bound on the number of
steps.

Each step, we can have two choices that
double the number of machines.

And each machine, potentially,
we have to copy an infinite tape for.

So this should start to give
us a sense that that should

be a lot of power that we
have with non-determinism.