Re: NP-complete and NP-Hard?



In article <pxb7jgnre31.fsf@xxxxxxxxxxxxxxxxx>,
Jean-Marc Bourguet <jm@xxxxxxxxxxxx> wrote:
>Bart Demoen <bmd@xxxxxxxxxxxxxxxxx> writes:
>
>> Torben Ægidius Mogensen wrote:
>>
>> > So NP-complete \subseteq NP \subseteq NP-hard.
>
>Is this true? I though that NP-complete is the intersection of
>NP and NP-hard.

There are NP-hard problems that are not in NP, and there are NP problems
that are not NP-hard, so \subseteq is the wrong operator. Yes, NP-complete
is the intersection of NP and NP-hard.

>> Also "NP-complete is strict subset of NP" - right ?
>
>Isn't this question equivalent to P ?= NP ?

Actually, it's easy to prove that NP-complete is a strict subset of NP,
but not in a satisfying way. NP-complete doesn't include the trivial
languages of the empty language and the language of all strings, but
NP does, so NP-complete is a strict subset of NP. Let NP' = NP without
the trivial languages. The question "is NP-complete a strict subset of
NP'?" is equivalent to "is NP != P?".
--
Daniel Jiménez djimenez@xxxxxxxxxxxxx
"I've so much music in my head" -- Maurice Ravel, shortly before his death.
" " -- John Cage
.