Next we're going to talk about

another very important aspect of this theory called NP-completeness.

So this starts with a very simple definition.

So any search problem,

a problem in NP said to be NP-complete if

all problems in the NP polynomial time reduced to that problem.

This seems like a very very strong condition but

actually it's pretty natural as we're going to see in just a second.

And the reason this class of problems is important,

is that there's a theorem that was proved

independently by Cook and Levin in the early 70s,

really about the same time as Carp was doing his reductions for practical problems.

That says that SAT is NP-complete.

Now, this is a result with amazing ramifications.

In a course in theoretical computer science,

you could learn this proof really in an hour and I don't have

the time to go through it in detail but I can explain the basic idea extremely briefly.

The idea is to take the idea of

a non-deterministic turing machine which is like

a specification of an algorithm of a search problem.

So, you take your problem and you formulate it as a non-deterministic Turing machine.

And that's true.

Any search problem you can do that.

That's the formal definition of a search problem.

And what the proof does is take that notation which is a particular notation

you could think of it as a mathematical notation

or states and Aeros the way we do it with label transitions.

And just convert that notation into SAT notation.

They're both discrete formalism and not really that long or difficult,

but that's what the proof does is get to the point

where given any search probably you can make

a non-deterministic turing machine and then you can convert that into an instance of SAT.

Which means that if you have an efficient solution for SAT then

you have an efficient simulation of that non-deterministic turing machine,

which gives an efficient solution to any problem in NP.

So non-deterministic turing machine goes to SAT instance and that's the reduction.

And again I'm very very much oversimplifying this proof,

it's really an amazing fundamental result.

So, the corollary to this means that SAT is tractable if and only if P is equal to NP.

Of course if P equals to NP it's tractable but also if

SAT is tractable then all the problems in NP are tractable.

So that means P equals NP.

So another way to do it is to say that assumption that SAT's

intractable is very much the same as assuming that P is not equal to NP.

And in terms of the practical problems,

here's what this theorem says.

It says that all those problems of parps are going to reduce to SAT.

All problems in NP have been reduced to SAT,

but then that reduces to all of them.

So what this means is that all the problems are NP-complete not just SAT.

If we can solve any one of these problems,

we can solve all the problems in NP.

That's a much, much stronger statement about the difficulty of solving these problems.

There are all NP-complete.

And all of those thousands and thousands of problems that

are formulated in scientific papers every year,

are NP-complete in the sense that if you can find an algorithm for

any one of them you have an efficient algorithm for all of them.

That gives us much more confidence about asserting the difficulty of finding

guaranteed polynomial times algorithm to solve them than just mere reduction.

So NP-completeness adds to our universes in the following way.

If it's not equal to NP then there's some intractable problems.

If it's equal there's no such thing, non-determinism would help.

If it's equal non-determinism is no help.

And again these are the different formulations that we looked at if P equals

to NP it's no more no harder to find an answer than to just guess.

P equals NP then there's

guaranteed polynomial time algorithms for all the problems un NP.

If it's not equal then you can prove a problem to be

intractable by doing a reduction from an NP-complete problem.

So the situation is a little bit more like this.

And again these are possibilities just based on the basic definitions that we have.

But still there's no progress on knowing which of these two things are true.

Despite the fact that many people have been working on it for decades.

So just a quick summary.

We have the class of all search problems that's NP.

The ones we can solve in polynomial time those are P.

And then we have the NP-complete problems which you

can think of as the hardest problems in NP.

And then the idea of intractability which if P is not equal to NP those are

the ones that are not in P.

And we have thousands and thousands of problems that are NP-complete.

And our idea about this theory is to use it as

a guide when faced with a practical situation.

If you have an NP-complete problem you need to know that finding

efficient guaranteed polynomial time algorithm for

that problem would be a stunning scientific breakthrough.

It would be proof that P is equal to NP.

And you should know that because you definitely will

confront some NP-complete problems in your career.

So, it's pretty safe to assume that P is not equal to

NP and that the NP-complete problem is intractable.

And so what you want to be able to do at a minimum is

identify these situations and proceed accordingly.

And we'll talk about ways of doing that in the next segment.

In the meantime if you're in Princeton if

you take a look at the west wall of the CS building,

you can see some indentations in the pattern of bricks.

And this is made really for students of this course.

If you take those indentations and treat them as binary numbers,

convert them to ASCII then you get the P equals NP question.

Now when this building was built in the late 80s a lot of people said the building,

s going to last a long time,

why would you put such important question that

so many people were working on into the brick?

Well actually now a couple of decades later

it's more important a symbol than ever of computer science.

And of course with just investing in a few bricks,

we could change the equals to and not

equals in the end or the question mark to an exclamation point without much work.