
Title:
0705 Proving NPCompleteness

Description:

So let's say now that you have a problem

that you know to be an NP such as vertex cover,

and there's basically two ways that you could show this problem to be NPcomplete.

The first one is, you could take another NPcomplete problem

and reduce it to your new problem.

A second way would be to use the definition

that we just had of NPcompleteness

and show that this problem here can be used

to solve any other problem that is also solvable in NP,

and by showing, I mean proving.

That is the first way, and the other way would be to

just use the definition of NPcompleteness that we just looked at,

so what you could also do is you could show,

or in this way you would have to prove mathematically,

that any problem in NP can be reduced to your problem.

And the emphasis here is on any problem,

because otherwise, it wouldn't be NPcomplete.

And those are the two possible ways you could show NPcompleteness.

I will call this here approach number one

and this one up here approach number two.

Now if you look at those two approaches,

this one here sounds much easier in a way than this one here,

because here we just have one problem where we have to have a reduction,

and here we have to have any problem.

Not even some problems, not even a million problems, but really any problem.

But there's a little problem with the first approach here,

and I hope you can tell me what that is.

So what could be potential issues with approach number one?

Could it be that this only works for some problems in NP?

Could it be that before we can do approach number one,

we must first have had success with approach

number two for at least one problem in NP?

Or could it be that approach number one is not always correct?

So please check all of these statements which you believe are true.