
Title:
P=NP  Intro to Algorithms

Description:

This brings us to a point where we can ask one of the most fundamental questions in theoretical

computer science and that is does P=NP and in particular, here's what we actually know.

This is true. We know that every problem that's in P is in NP and every problem that is NP is in EXP,

that is to say any problem that you can solve in polynomial time,

we can certainly solve in nondeterministic polynomial time,

and any problem that we can solve in a nondeterministic polynomial time,

we can also solve in exponential time, but here's what we don't know.

It could be the case that the class NP is actually equal to the class EXP.

That is to say the set of problems that we can solve in a nondeterministic polynomial time

might be exactly the same as the ones that we can solve in exponential time.

So there's a sort of outer set and that's distinct from say this inner set,

which is the set of problems that are solvable in polynomial time.

There's one other thing that we know, we do know that there really

is a difference between polynomial and exponential time.

There's some problems that can be solved in exponential time that are definitely not NP.

So we know those two things are different, but we don't really know.

It could be that NP is equal to x. It could also that P is equal to NP.

So the problems that we can solve in a nondeterministic polynomial time

might be exactly the same as the ones that we can solve in polynomial time,

which both would be then different from exponential time

or could very well be that there are really three different categories here.

That problems that are in NP don't necessarily require exponential time,

but they may not be solvable in polynomial time eitherwe don't know.

So this question of whether or not P=NP, whether we're in this case here is a pretty heavy question.

So what happens if P does equal NP. Well, a lot people say a lot of different things.

Let's turn this into a quiz to see what you think.

So one possibility is that cryptographic protocols, so things were keeping secrets in encrypting data

that are based on problems like factoring that are in NP could be cracked.

Another is that there's a whole lot of computer science theoreticians

who will be suddenly out of work because they will no longer be having to think about this problem.

Another possible outcome might be that with P equal to NP

that means the computers will be smarter than people.

They will be able to solve problems fast that people can't.

So I don't know, just tell me which one you think is true.