---
Video Title: Main Themes of Course
Description: Theory of Computation
https://uvatoc.github.io/week12

26.1 Wrap-up: Main Themes of the Course

David Evans and Nathan Brunelle
University of Virginia
---

What are the biggest themes in the class?

We'll start with the
one that is most close to

computing models,
which I'll call universality.

The main thing that we looked at computing
models for...

There are lots of different reasons we
define computing models.

The biggest one was
the fact that all these

properties about computation
seem to be universal.

So what are examples of places where we
saw universality?

Yeah, I don't know.

Yeah, so we saw just a NAM gate is enough
to compute every Boolean function.

We can compose them in a circuit.

We can compute every Boolean function with
enough NAM gates.

And we saw other sets of gates that are
also universal.

So this is a very powerful
notion that there aren't

all these ad hoc different
notions of computing.

Once you have this notion of Boolean
functions and circuits, there are lots of

different things that end
up computing this universal

set of all the things you
can compute with a function.

Of course, you're defining that set in
terms of your computing model,

But the fact that it's so
robust and that you need a

very small amount to define
that set is very powerful.

And we saw other examples with Turing
machines.

We've seen that a very simple model of
computing, and we've seen a few variations

on Turing machines, they can compute every
computable function.

So what's a computable function?

A function that can be computed with our
model of computing.

So that's a very circular notion.

But the Turing thesis is sort of saying
that it's kind of a circular notion,

But it corresponds to our notion of what
any machine that we can build in this

universe, or any universe we can imagine,
can compute.

And we also saw even
the cost... this is where

we ended up with this
class of polynomial time.

The cost can be defined very robustly,
even if we vary properties about the

machine, like whether it's a RAM machine
or a tape machine.

The costs change, but within this large
computing cost class are the same.

So I group all those as being related to
universality.

Another theme that we've seen in lots of
different ways across this, and it is

related, at least how we showed universality
in a lot of those cases was simulation.

And I'm going to call out
simulation as what we're

doing in simulation is using
one thing to do another.

We're able to simulate one kind of machine
with another machine.

We're able to solve one problem with
another problem.

All of these are kind of variations on the
same idea of simulation as a way of

showing equivalence, or showing that one
thing is more powerful than another.

We saw a simulation that we
can simulate a Boolean circuit

with a NAND-Circ straight
line program, and vice versa.

That means they're equivalent
if one can simulate the

other, and the other can
simulate one in both directions.

And we saw the same thing with gate sets
for Boolean circuits.

And we saw in cases where maybe one
direction is really obvious, we saw that

we could simulate a non-deterministic
Turing machine with a Turing machine.

That one is no more
powerful than in the other

direction, the equivalence
is there as well.

So that could have been in the other
category.

And our uncomputability and hardness
proofs are kind of like this as well.

They're maybe not the same as simulating
one machine with another, but we're saying

if we had a machine that could do X,
we could use it to do Y.

We could build something using that
machine to do something else.

So I think these are all
at some level connected to

the idea of using simulation
to show equivalence.

Okay.

Counting.

We've used counting a lot.

I think you probably thought you knew how
to count before this class.

Hopefully you still know how to count.

Although it's more complicated than you
thought maybe.

Wherever we use counting.

Why is counting such a powerful idea?

Yeah.

Good.

Yeah.

So we've used counting to show things
don't exist.

To show there are functions that we can't
compute.

That our way of measuring cost is
counting.

If we're trying to understand in a formal
way the cost of doing something,

that's almost always a counting problem.

So we've seen counting lots of places.

I think that real powerful ones are these
proofs that we've done.

And we've seen two examples, ones that I
think are most important.

We showed that the number of
Boolean functions of size input

n is greater than the number
of circuits that are small.

Where we had a more
precise than small in

quotes definition of
what it meant to be small.

By just counting and comparing the number
of functions to the number of circuits,

that said there must be some functions
that are hard to compute.

That we need a large circuit to do.

And then when we extended
that to uniform computation,

we said, well, now we
need a Cantor's result.

Now we're dealing with infinities, but
there are different kinds of infinities.

That they're uncountable versus countable
sets.

And the number of functions is
uncountable.

And the number of Turing machines is
countable.

Turing machines is just the way we chose
to represent computation formally.

But anything where we
can write down programs in

a finite length string is
going to be countable.

We're not going to be able to have a
program that corresponds to every function

because the number of functions is
uncountable.

So this is a very strong and robust
result.

Okay.

This is a theory class.

Most of what we've done in this class has
been about we have some mathematical model.

And based on that mathematical model,
we can prove things.

We can reason about some things are
possible, some things are not.

Some things are equivalent, some things
are not.

Some things have this cost, some things
have that cost.

All of this is in this mathematical
abstract domain.

Mathematical models are really powerful.

They allow us to make things precise.

They allow us to use all the tools of
logic.

Use all the tools of logic and formal
reasoning to get really precise,

strong, robust answers.

This is the kind of thing that we can do.

And why we end up with these definitions
of complexity classes like NP complete,

where we can answer very precisely for any
problem, whether or not it's in the class.

And once it's in the class, we know all
sorts of things about it.

We know that unless p equals NP,
there's no efficient solution to it.

All of these things that we have from
these abstract mathematical objects that

we've defined and reasoned about give us
ability to have really robust,

strong answers that follow from using logic
in a way that should be incontrovertible.

At least we should be able to write proofs
that everyone who agrees with our logical

formulation and agrees with our axioms
will agree to.

But there's a lot of limits.

Everything that we're doing with these
mathematical models is not reality.

Our models are not the same as real
computers.

Our models can be infinite.

Having infinite models is really useful.

It allows us to say robust things.

If we didn't have infinite
models, every problem

that we defined would
say an input up to this size.

Or this limited set of inputs,
it would be a finite problem.

Much less interesting to talk about.

But of course, real machines have limits.

Any real machine is going to be finite,
which is really different.

And part of what we did in the first part
of the class where you talked about.

Boolean circuits was, well, those were
finite.

So at least there was a stronger
connection between real machines.

But also those are very simple
models that couldn't capture

the things that we think of
real computers being able to do.

Our mathematical models are never going to
capture the properties of the physical

world that impact what happens when real
machines run real programs.

But they are going to give us useful
insight, give us ways to understand what

makes problems hard and what we can do
when we encounter hard problems.

And at least we hope if you've developed
some sense that these are actually fun,

interesting puzzles that have their own
intellectual value.

A lot of the reason we want to do theory
on mathematical models, it's really for

its intrinsic value, which sometimes you
can relate to, yeah, this is a practical

problem that is going
to help you build your

computing system that
will take over the world.

But often there's a pretty big gap there.

And it's actually really important to make
sure that all the theoretical results,

you realize you're getting them with a
model.

And you're getting them
based on assumptions

that are not ever true
about real systems.

The model that we've
seen the most in at least the

last half of the class is
the turning machine model.

Our mathematical models take all the
complexity of a real computer or of what

we're trying to model
and can turn it into

something that fits
pretty well on one slide.

There's no way you could
describe what's going on on

your actual processor on
your laptop on one slide.

Intel's instruction manuals
are thousands and thousands of

pages and they don't describe
everything that's going on there.

Okay, so with that setup, what does it
actually mean in practice?

What can we say about a
problem once we've done

this theoretical proof
that it's NP-complete?

The size of the input that we want to
evaluate Q on increases.

What can we say?

Well, we should be careful not to say
non-polynomial.

We can say, like, at least the best-known
solution, given what we know, there isn't

a solution that is going to cost
polynomial time.

Good.

Yes.

Yeah, our definition of class NP and being
NP-complete means it is in class NP.

So there exists some witness that we could
use to verify.

How does that help us practically?

It takes a long time to compute it, but
you can prove that it's correct quickly.

And there are lots of cases where that's
actually very useful.

So that does say solutions can be verified
efficiently.

Here.

Yeah.

So it sounds like, at
least based on what we

know today, we probably
don't have a solution.

So do we know it's always going to be
expensive?

Remember, what we've proven is there's
some inputs.

By proving that it's NP-complete, we
can use it to solve other hard problems.

It doesn't mean that it's hard for every
input.

All it means is that for some inputs,
but it might not be hard for all inputs.

And this is actually a really important
distinction.

It's really useful to have problems that
you know are hard if you want to do

cryptography, because your goal is to have
a problem that is hard for an adversary to

break, but you have some backdoor that
allows you to, if you have the key or you

have some extra information, to solve it
quickly.

And people have tried to
build cryptosystems based on.

NP-complete problems,
thinking this means it's hard.

In order for it to be useful for
cryptography, you have to know that the

instance of the problem is actually a hard
one.

And if you pick a random instance of most
NP-complete problems, at least depending

on the problem and
how you pick it, there's

no guarantee that a
random instance is hard.

There have to be infinitely many instances
that are hard.

If the number of hard
instances was finite, well

then, it wouldn't actually
be a hard problem.

You could have a lookup table for those
ones and all the other ones are easy.

So there have to be infinitely many ones
that are hard, but that doesn't mean that

a randomly sampled one or a not carefully
generated one will actually be hard.

And what we've seen with
satisfiability, for many of the

problems that occur in
practice, they're actually not hard.

Even if the problem is NP-hard,
often particular inputs are easy.

And of course, there may be good ways to
approximate.

There may be good ways to
approximate it that are perfectly

useful for the problem we
actually have to solve in practice.

Being NP-hard just means we can't get the
optimal answer all the time without having

work that's more than polynomial,
assuming P is not equal to NP,

or at least based on what we know about
algorithms today.

You have to be careful what it means in
practice is not necessarily that every

instance or even the instance you have to
solve of this problem is actually hard.

Moving in budget