Re: NP-complete and NP-Hard?

Shashi wrote: 
Bryan Olson wrote:

Bart Demoen wrote:
> Also "NP-complete is strict subset of NP" - right ?

Right.



"NP-complete is strict subset of NP" iff P!=NP ?


As others have pointed out: the empty language is in P,
and it is not in NP-complete (whatever the outcome of the
question P=?NP).

Because ... under the relation "is polynomially equivalent to",
P has three equivalence classes; one class consists of the empty
language, one class is the language consisting of all strings, the third
class contains all other languages (neither empty, nor the whole of
$\Sigma^*$); since NPC itself is an equivalence class, NPC can't be
equal to P.
The definition of "transforms polynomially into" has a crucial iff that
is missed often.

Cheers

Bart Demoen
.