. Today, we're going to talk about
intractability in our last lecture. this
is an appropriate topic to close the
course on because it really lays out for
us some of the big challenges of the
future. most people are taking this course
because they're going to want to be
involved with algorithms, algorithms in
the future. and this topic really helps us
lay out what's ahead. As an introduction,
we'll review some very, very basic
questions about computation. Some of you
may be familiar with this subject area
others may not be at all. So, it will just
be a brief review in either case. But some
of the concepts are relatively easy to
understand and so, and they lay a good
background for starting with computation
with intractability. We need to think
about computation itself first. There are
these kinds of questions that came up
actually about the same time or even
before computers actually were invented or
came into use. Now, what is a general
purpose computer? What does that mean? are
there limits on the power of digital
computers? That's another interesting
question. Are there limits on the power of
any machine that we can build? this kind
of question with the outgrowth of similar
questions on mathematics that was posed by
David Hilbert in the beginning of the
twentieth century. and there were some
very profound thinking going around
Hilbert's questions, and later, around the
questions on computers that initially were
related, but then took on a new life of
their own. To take a look at the idea of
what these mathematicians were thinking
about in the middle of the twentieth
century that we call the simple model of
computation that we looked at when we were
working with the KnuthMorrisPratt
algorithm. so what we did was we imagined
a, a machine, an abstract machine called a
discrete finite automaton or an FSA, a
finite state automaton. that is a very
simple machine where we imagine that it's
got a tape that has the input. that's just
a long strip that's divided into cells.
It's got a finite alph, alphabet of
symbols and it had a tape head that could
read one symbol from one cell of the, of
the tape. And then, based on what it saw,
it would move to a different state. It
would move one cell at a time, read up all
the tape, all the input, and if it got to
the right state, we'd say it'd accept it.
That's what we did with KnuthMorrisPratt
was we imagined this machine and then we
built a program that now constructed a
table which just said what to do, which
state to go to for each symbol on the each
possible symbol on the tape for each
state. and then that was a way that we got
this problem solved. in, a natural
question arises when mathematicians and
theoretical computer scientists first
started taking a look at abstract models
of computation like this is, can you make
them more powerful, is there a more
powerful model of computation than DFA?
Well, it didn't, it didn't take long to
realize, of course the, there's a more
powerful model. And actually, the progress
was almost incremental. You can think of
it as being almost incremental where you
just add a little bit of power to the DFA
that we can show, that makes that more
powerful but, but what's the limit? and
actually the, the limit was proposed very
early on by Turing in here at Princeton in
the 1930s. it's a universal model of
computation where just like the DFA, we
imagine a machine that has a finite set of
states. but instead of just reading the
tape, it can write on the tape as well and
it can move in both directions. so, it, it
can store intermediate results on the
tape. but, other than that, it's very
similar to what we imagined for the FSA.
And now the question is, is there a more
powerful model of computation than this
one? and the remarkable fact is that
Turing answered this question in the
1930s. Actually, he did the work just
before he got here to Princeton, and then
finished the paper. He said, no, there's
no more powerful model of computation. In
fact, many of hailed this as the most
important scientific result of the
twentieth century. because it, it tells us
really wha t we need to know about the
power of the machines that we build. so
with Church, who was Turing's adviser here
at Princeton, the we have the thesis that
there's no more powerful machine. Turing
machines can compute any function that can
be computed by a physically harnessable
process of the natural world. Now, this is
not a mathematical theorem because it's a
statement about the natural world. It's,
it's not something that you can prove from
basic principles. but it is something that
you can falsify, you can run an experiment
that shows it not to be true. And the
whole idea behind this thesis and, and
behind Turing's proof about abstract
models of computation is that and we've
seen it many, many times. So, we can use
simulation to prove model equivalence. So,
we wrote a Java program to simulate a
discrete finite automaton, and that means
that Java's at least as powerful as that.
you can write people have shown you can
write Turing machines that simulate the
operation of, of store program computers,
like the one's that we use. Or if you use
an iPhone and you're running an app that's
written for the Android or vice versa,
that simulation that proves models that
are equivalent, demonstrates that models
are equivalent. And that's been an
extremely effective way for us to
understand that different computers have
similar capabilities. That, you know,
you're not going to compute more by build,
building some new machine. so these had
profound implications. And, it's, it's
really amazing that Turing came up with
this so long ago really before computers
came into use at all. and it means that we
don't have to try to invent a more
powerful machine, or, or language and it
really enables rigorous study of the
computation that we can expect to do in
the natural world. so that's the basis for
the theory of computation. And it's, it's
related to the study of algorithms. but,
because it gives us a simple and universal
model of computation. But we haven't
talked about efficiency. how long does it
take to simulate an Android to s imulate
an iPhone and so forth? So, what about
cost? what about time? That's been our
focus when developing algorithms. and what
we want to think about next is how to deal
with that cost. but first, I just want to
lay out the evidence that we have for the
Church-Turing thesis. That is, it's been
eight, eight decades and nobody's found a
machine that can compete more than we've
been computing with the machines that we
have. And the other thing that was really
convincing to the mathematicians in the
mid-20th century is that people tried all
different types of models of computation.
Church was working on something called the
un-typed lambda calculus, which actually
is the basis for modern programming
languages. And there are other
mathematicians working on recursive
function theory and grammars and other
things. And eventually, essentially, they
were all able to use these languages to
express the formalism of another one, and
then therefore, prove them to be all
equivalent. And that comes in through to
the modern day with all programming
languages. You can write a simulator or a
compiler for one programming language and
another, or a different random access
machines, simple machines, like cellular
automaton. and even computing using
biological operations on DNA. or quantum
computers that you may have heard about.
all of these things have turned out to be
equivalent. So, there's a, a lot of
confidence that the Church-Turing thesis
holds. but what about efficiency? So, this
is a similar starting point for the study
of algorithms. What algorithms are useful
in practice? so in order to know what the,
what useful we're going to consider time
and we're going to say that it's an
algorithm that it's not just that it's in
theory, would, would complete the problem
is that it actually would solve the
problem in the time that we have
available. and just to set a dividing
line, it a, a, a clear bright line it, it,
we're going to say is that we'll consider
it to be useful in practice or efficient.
If it's running time is guaran teed to be
bounded by some polynomial in the size of
the input for all inputs. and for the
purpose of this theory, we don't even care
of what the exponent is, could be n to the
100th. now you might argue that's not a
very useful dividing line but it is a
useful starting point. and as you'll see,
even the starting point has told us a
great deal about the kinds of algorithms
useful in practice. and, this was, this
work was started in the 50s.' also, here
at Princeton. and many, many people looked
at models for trying to understand what,
what this meant. the dividing line is
between polynomial as, as I've said, and
exponential. Exponential is a two the, the
n-th power of some constant of greater
than one to the n-th power. And we'll talk
about that in just a second. so sorting is
useful. It, so anytime it's bounded by a
polynomial or, but here's another one
which is finding the best traveling
salesperson tour on endpoints. if you're
going to try all possible tours that
algorithm is not useful in practice
because n factorial is not bounded by a
polynomial in n. Its running time actually
grows like n to the n-th. so, this is a
useful starting point for our theory
because it's very broad and robust. and if
we can put some algorithms in the class
with sorting and other algorithms in the
class with traveling salesperson using
brute, brute force search, that's going to
be useful. It'll tell us which algorithms
we want to use. We definitely can use the,
think about using the first but we can't
think about using the second. and, and
actually, unlike turing machines, where we
wouldn't actually kinda play turing
machine to solve a practical problem. in
this theory, it's often the case that the
polynomial time algorithms will scale to
help us solve large problems because the
constants usually tend to be small. but
the, the key is the idea of exponential
growth and I just want to be sure to
convince everybody that it's not about,
when it comes to exponential growth, it's
not about the technology. That is a
dividing line th at no matter how fast
your computer is, you can't be running an
exponential algorithm and expect to be
solving a large problem, in just a thought
experiment to reconvince everybody of
that. So let's suppose that, imagine that
we had a huge, giant, parallel computing
devices. This thing is so big that it's
got as many processes, processors as there
are electrons in the universe. So, we have
a supercomputer on every electron and
we'll put the most powerful super computer
we can imagine today on every electron in
the universe. and then, we'll also run
each processor for the lifetime, estimated
lifetime of the universe. so, how big a
problem can we solve? Well, it's estimated
there's ten to the 79th electrons in the
universe and supercomputers. Nowadays,
maybe can do ten to the thirteenth
instructions per second. and you can
quibble about these numbers and make it
ten to the twentieth if you want. it's
estimated the age of the universe in
seconds is ten to the seventeenth.
And if you don't like that, make it ten to
the thirtieth.
You multiply all those numbers together
you're going to get a, a relatively small
number to say a thousand factorial. ten to
the seventeenth times ten to the
thirteenth times ten to the 79th is only
ten to the 109th or something.
Whereas a thousand factorial is way bigger
than ten to the 1000th. It's more like
1000 to the 1000th, alright? So, there's
no way that you can imagine solving a
thousand city TSP problems using that
brute force algorithm. You can let your
computer run but it's not going to finish.
technology is out of the picture when we
have exponential growth. So, that's why
it's so important to know algorithms are
going to require exponential time and
which ones aren't. in this theory it would
seem. let's at least get that
classification done. so which problems can
we solve in practice? We're just going to
say that the polynomial time algorithms
are the ones that we can solve in practice
that guaranteed polynomial time
performance. so that brings us right to
the question, which problems have
polynomial time algorithms? and
unfortunately, it's not so easy to know
that. get stuck right away on trying to do
that classification, and that's what
today's lecture is all about. so, this is
a similar bird's eye view to when we
introduced the classifying algorithms when
we're talking about reduction. And
reduction's a very important tool in this
theory as well. So, what we're going to
say is a problem is intractable if you
can't guarantee that you can solve it in
polynomial time. so what we want to do is
prove that the problem's intractable.
there have been a couple of problems that
have been proven to require exponential
time. but they are a bit, artificial.
well, so here's one. Given a constant size
program, does it halt, and in most case
that's or here's another one. Given an N
by N checkers board, can the first player
force a win if you have the force capture
rule? Well, N by N checkers board for
large N is again, that's a, certainly a
toward problem. But for the many real
problems that we actually would write
this, like to solve, unfortunately,
there's been very few successes in proving
that a problem is intractable. So even
though it would seem that you would be
able to be able to separate problems that
can guarantee problems polynomial times
solutions from problems that require
exponential time for some input, there's
been very little success in proving that.
but that's an introduction in a motivation
for the theory of intractability.