---
Video Title: Tractable and Intractable Problems
Description: Theory of Computation
https://uvatoc.github.io/week11

23.1 Tractable and Intractable Problems
- Complexity Class P
- Exponential Time
- "Tractable" and "Intractable"

Nathan Brunelle and David Evans
University of Virginia
---

Last time we introduced a definition of
running time.

We said that it was essentially the number
of steps that a Turing machine is going to

need in order to provide an output for an
input of a particular size.

So if you recall, running time in this
case was actually a function, not a

number, that said, here's how many steps
you need for an input of size in.

Given the size of your input, the output
is the number of steps you'll need.

And we also talked about some complexity
classes for time, where we said time in

said that for an input of size in,
we ran an at-most n step.

So in this case, the complexity class time
of n is the set of all functions that will

compute and say less than or equal to n
steps for an input of size n.

In this case, this is saying t of n is
equal to n.

So this is saying that any function which
has an algorithm or a Turing machine that

will halt within t of n steps for an input
of size n, where in this case,

t of n happens to be equal to n itself.

Very often, when we're trying to
categorize problems, we make this sort of

seemingly arbitrary divide between two
groups of run time.

Those being polynomial time and
exponential time.

So we say that some algorithm
or some Turing machine is a

polynomial time Turing machine,
or it runs in polynomial time.

If we can show that the running time for
that Turing machine, like t of n,

if that function, which is the running
time of that Turing machine, belongs to,

let's say, big O of n to the c for some
constant c.

So if that's the case, I don't care what
the constant is, as long as I can find

some constant such that t of
n belongs to big O of n to the

power c, then we can say that
that was a polynomial run time.

On the other hand, we can have
exponential run time, which says

we can have t of n belongs
to big O of 2 to the n to the c.

So that is 2 to the power of some polynomial
makes that an exponential run time.

So if I can find any c such that t of n
belongs to big O of 2 to the n to the c,

then that means that that was an
exponential running time.

And very often, this is the line,
whether it was polynomial or exponential

time, that a lot of computer scientists
like to draw as a demarcation.

We tend to concern ourselves a lot with
whether or not we can solve a problem in

polynomial time, or if that problem is
going to require exponential time.

This seems somewhat arbitrary why we have
this divide.

There are a few reasons why we like it.

First of all, I mentioned this strange
pattern last time, where most natural

problems either require a
small degree polynomial,

like n squared, or else
require exponential time.

So just sort of, as we're coming up with
problems we would like to solve,

they naturally divide themselves in this
way anyway, that most of them are going to

be either really, really small polynomial
or else exponential.

So by looking at this divide, that
actually pretty well matches our

real-world experience of which things are
going to be easy to solve, or which

problems will be fast for computers to solve,
versus which ones are going to be slow.

Typically we say polynomial means fast,
exponential means slow.

There's a few other reasons for this as
well.

If we look at polynomial time,
we had mentioned last class that the

category of a problem, how
efficiently we could solve it,

oftentimes depends on the
model of computation we're using.

So for instance, we
talked about those tape

model Turing machines
or RAM Turing machines.

They could have slightly different running
times for different problems.

In this case, if we're talking about any
polynomial, if we just care, does there

exist some C, then oftentimes this is more
tolerant of different computing models.

Doing this divide of polynomial versus
exponential tends to be more tolerant of

different computing models, whereas other
divides may or may not be.

Another reason for this is there's
something called Moore's Law.

Moore's Law basically says computing power
grows exponentially.

So that means that just over time,
because of the way that computers gain

their power, they sort of make more
progress towards solving polynomial time

algorithms than they do exponential time
algorithms.

The increase in power of the machines
outpaces the difficulty of solving the

problem for a polynomial time problem,
whereas for an exponential time one,

it kind of matches the pace rather than
exceeds that pace.

So essentially, when we're talking about
whether or not problems are efficient to

solve or inefficient to solve,
we often ask this question, can we do it

in polynomial time or must we do it in
exponential time?

Does it require exponential time?

So the question of is
this efficient is usually is it

polynomial versus is it
exponential for these reasons.

And we call this question, is it
efficient?

We often call that tractability.

Is that problem a tractable problem versus
is it an intractable problem?

Where the vague notion
of tractable means that it's

feasible for us to solve
this in the real world.

The notion of intractable
means it's kind of

impractical for me to
try to solve that problem.

In real world experience,
what's tractable versus

what's intractable really
depends on the use case.

If I am Google, I probably
have problems that

are differently
intractable from you all.

Because Google is working
on the order of petabytes

for various algorithms
that they're writing.

So if you're running quadratic in terms of
petabytes, that's bad.

If you're running quadratic in terms of
the test case that Aaron Bloomfield wrote

for your 2150 problem, that's probably
pretty okay.

However, for most theoretical purposes,
we consider tractable to be polynomial

time and intractable to be exponential
time.

So for now, that's going to
be the formal dividing line for

whether a problem is a tractable
problem or an intractable one.

Whether we can solve it in polynomial
versus exponential time.