0:03

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.