
Title:
1046 Border Between NPComplete And P

Description:

Now, before the end of this unit, two words of caution.

The first one is that the border between NP completeness and polynomial time

can sometimes be very thin.

I already mentioned to you that for example 3SAT,

so where you just have three variables in each clause is NP complete

but 2SAT where you just have two variables is solvable in polynomial time

and there are many other cases like that

but of course this is good news

because if your problem turns out to be just as hard to solve as 2SAT

you actually have a polynomial time algorithm for it

although it might initially have seemed a bit harder

or sometimes even if your original problem possibly is as hard as 3SAT

maybe you can look at a slightly different problem that becomes polynomial time solvable.

Because oftentimes there are many different ways to frame

the practical problem that you're trying to solve

so sometimes you're lucky there.

The second thing is an actual word of caution.

Because this border here can sometimes be so fragile.

It's very important to be precised in your NPcompleteness proof.

Because sometimes making just a little mistake in an NPcompleteness proof

can invalidate this whole proof and of course we don't want that.

Now, it's time once more to congratulate you.

You now know what NP completeness means and how you control NP completeness.

And actually not many people can do that.

Very few people know precisely what NP completeness means

and also they're not capable of showing NP completeness.

In the next unit, we're going to take you even one step further.

We're going to show you countermeasures against NP completeness.

Because even most people that understand what NP completeness means

and that can also show NP completeness actually tend to give up

once they've shown their problem to be NP complete.

But that's actually not necessary because there are many many techniques

that she can use to attack even NP complete problems.

What should you do when you want to solve the problem and show that is NP complete?

Should you carefully check your proof?

Should you have somebody else carefully check your proof?

Should you give up?

Should you maybe try to think about ways of modifying your problem

so that it could not be NPcomplete or

should you try to use the techniques that you're about to learn in the next units of this course.