Okay. We're going to finish up by talking
a little bit about different approaches to
dealing with needing to solve intractable
problems. this, actually, a lot of
different ways to proceed when you run
into an intractable problem. One idea is
to exploit it. In fact, an example of
this, a very successful example of this is
modern cryptography. People using the
internet for commerce, or for interaction
through digital signatures and other
mechanisms are absolutely relying on
modern cryptography for security and
privacy. and that's all based on the RSA
cryptosystem, or much of it. and it's
based on the idea that multiplying two
N-bit integers is relatively easy. This
and a, brute force multiplication
algorithm gets it done in quadratic time
when there's faster ways. So that's
polynomial time. So in order to encrypt
something, you need to multiply things,
but in order to break something, you would
need to factor things. That's exploiting
interactability. Nobody knows a good way
to factor. A factor is not MP complete, by
the way, not known to be MP complete. So
it doesn't, in fact, not quite as hard as
other problems. But still nobody knows a
fast way. So but this is an example of
exploiting suspected problems, that's
suspected to be intractable. In fact,
there's other ways to make money [UNKNOW
put, put some challenges and go ahead and
factor this number towards $30,000. . Some
of these things have been , prices have
already been claimed but it may be easier
to go after this than after the, the
millionth and actually [UNKNOWN] and
Idilin were just not just but professors
at MIT when they came up with this and
they realized that. the important
commercial potential of this And actually
created a company based on the difficulty
of factoring that sold for 2.1 billion
dollars not that long ago. And it's the
basis for, internet commerce. so these
possibilities for making a lot of money
out of, understanding the difficulty of
computation, are not imaginary. they're
quite real. so, I, talk briefly about the
complexity of fac tors.
That's, another problem like, LP is that,
it's current status is what LP was in the
70s. we're using it, a lot of people were
doing it we knew that the worst case was
of simplex was exponential. we'd like to
classify it, like to know if there's a
poly time, nomial time algorithm, but
nobody knew one. And then the big surprise
for LP was that Catching came up with a, a
polynomial time algorithm and, and, then,
you know, and people went to work. For
factor we're kind of in the same
situation. It's NMP. Being as we saw, it's
just a, search problem but. , it's not
known or believed to be either NP or NP
complete. But again who knows. so what if
it turns out that P equals NP. so, so that
would mean that now it factors in P and
that would . It's not just the math. that
would mean, there'd be an easy way to
break the, RSA crypto system which is in
wide use. people could, break codes by,
just by factoring. and that, that would
not be a good thing for the modern
economy. actually, something that
attracted a lot of attention, although
it's almost twenty years ago now. was a
result by Peter Shore that said, that,
There's a device, not quite a real device,
called a quantum computer. At least one
that you can imagine building that solves
factoring in polynomial time. So that
raises the question of, do we still
believe the extended Church-Turing thesis.
There are plenty of people that are not so
sure and are working hard on trying to
build devices that might have a big impact
on this kind of theory. well, actually we
create, and has created a, a new theory
based on how difficult is it to do things
with these sorts of devices. Okay, but in
general, suppose you have a intractable
problem, what are you going to do to cope
with it? Well, there's a number of things
that people have done really successfully.
so remember what it means to be
intractable. so a problem's intractable
if, in, in, in the sense that we don't
know a polynomial time problem that's
guaranteed to solve any instance. Now so
maybe you can give up on, on, on e of the
three key features of that statement.
maybe we don't care if we can solve every
possible instance. Maybe it's only the
instances that are gonna arrive in the
real world, arise in the real world that
matter. so or maybe you can even simplify
the problem and that's the one that you
really need to solve. So for example, if
you restrict. Satisfiability to have at
most two literals per equation, can solve
in linear time. Or even if you just insist
that there be at most one of the literals
per equation be not negated. That's called
a Horn-SAT. There's a linear time
algorithm for that. So maybe your problem
is you're trying to solve too hard a
problem, and you can come up with a more
special case of the problem that's
actually the one you want to solve that
you could solve. So that's definitely one
way to cope with interactability. another
thing is optimality. we've been talking
about search problems but this is, this is
more a statement about Mm-hm, . But,
optimization problems, we're looking for
the best solution or we're looking for a
proximate solutions. where you take away
the guarantee that the solution's perfect
in some way. So for example, the traveling
sales person problem. People can find ways
to get tours that are close to the best
possible tour, but maybe not the best. And
there's many, many other example of this.
Where people are looking for good
solutions, without trying to guarantee
that they're optimal. And those, maybe
those solutions are very close to optimal,
or at least, close enough that you can use
the solution and move on. if you
understand the quality of the solution
that you have, that might be, good enough.
But and again, the idea of approximation
algorithm and where you really can prove
what the quality is. So for example
there's a max three set that guarantees to
satisfy seven-eighths of the clauses. And,
actually these algorithm they're really
coming at the fine line between what's
tractable and intractable. And so, for
example the, if you want to do 7/8's plus
anything then it mea ns that P equals MP,
if you can do that in polynomial time P
equals MP there are lots and lots of
amazing results of this sort out there.
but anyway, in practice relaxing
condition, that you find the perfect
solution sometimes can get a long way in
practice. and then the other thing is
guaranteed polynomial time. We're talking
about worse case behavior. but there's
solutions out there. for example, there's
a SAT solver that was done here at
Princeton that can solve 10,000 variable
SAT instances. Or, as we, as I mentioned,
there's solvers out there for integer
linear programming that will solve huge
instances of real world problems. Worst
case behaviour may be observed in a real
world, might even be hard to find real
world problems. This is, definitely a lot
of room here, to not find solutions that,
might be efficient for the class of
problems, that you want to solve. and I
just want to finish up with one of the
most famous NP complete problems which is
the so-called Hamilton path problem. and
so that's given a graph, you want to find
a path that visits every vertex exactly
once. And simple path, so I can't reuse
any edge. So that's a solution to the
Hamilton Path probelem for this graph.
Another way to characterize it is a
longest path problem, longest simple path
problem in a graph. If you have one of
visit every edge eactly once, that's not
difficult. It's actually in the book. But
Hamilton path is NP complete. that's a
natural problem that's MP complete. and
actually this is it's empty incomplete,
but here's a really simple exponential
time algorithm for computing the Hamilton
path. it's just our depth for search
algorithm where we mark nodes and
recursively go through all the edges all
the vertices adjacent to the current
vertex. and if they're not marked, go
ahead and visit them recursively, marking
all the nodes that we see. The only
difference from the depth first search, is
this thing here. Where, when we're done,
with our recursive call on a node we,
unmark it. And what that does is make this
code try a ll possible paths. And there's
an exponential number of paths. so, so
define program for doing it for small
graphs. But it's going to take exponential
time for big graphs. But the longest path
problem is NP complete, and we're going to
finish up with a, a, a song that was
composed by a John Hopkins student, one
time when he was having trouble, thinking
about this idea. Woh, oh, oh, oh, find the
longest path. Woh, oh, oh, oh. Find the
longest path. Woh, oh, oh, oh. Find the
longest path. If you said P is NP tonight,
there would still be papers left to write.
I have a weakness, I am addicted to
completeness. And I kep searching for the
longest path. The algorithm I would like
to see is of polynomial degree. But it's
elusive, nobody has found conclusive
evidence that we can find a longest path.
I have been working for so long. I swear
it's right, and he marks it wrong. Some
how I'll feel sorry when it's done, GPA
2.1 is more than I hope for. Gary,
Johnson, Karp and other men (and women
too). Tried to make it order N log N. Am I
a mad fool if I spend my life in Grad
School, forever following the longest
path. Woh, oh, oh, oh, find the longest
path. Woh, oh, oh, oh, find the longest
path. Woh, oh, oh, oh, find the longest
path. that's a fine sentiment on which to
end this class on algorithms. I hope that
all of you out there are inspired to face
the computational challenges of the future
with the algorithms and the concepts that
you've learned in this class. so, that's
all. Keep searching, so long.