Re: NPcomplete and NPHard?
 From: djimenez@xxxxxxxxxxxxx (Daniel A. Jimenez)
 Date: 21 Jun 2005 09:28:52 0500
In article <pxb7jgnre31.fsf@xxxxxxxxxxxxxxxxx>,
JeanMarc Bourguet <jm@xxxxxxxxxxxx> wrote:
>Bart Demoen <bmd@xxxxxxxxxxxxxxxxx> writes:
>
>> Torben Ægidius Mogensen wrote:
>>
>> > So NPcomplete \subseteq NP \subseteq NPhard.
>
>Is this true? I though that NPcomplete is the intersection of
>NP and NPhard.
There are NPhard problems that are not in NP, and there are NP problems
that are not NPhard, so \subseteq is the wrong operator. Yes, NPcomplete
is the intersection of NP and NPhard.
>> Also "NPcomplete is strict subset of NP"  right ?
>
>Isn't this question equivalent to P ?= NP ?
Actually, it's easy to prove that NPcomplete is a strict subset of NP,
but not in a satisfying way. NPcomplete doesn't include the trivial
languages of the empty language and the language of all strings, but
NP does, so NPcomplete is a strict subset of NP. Let NP' = NP without
the trivial languages. The question "is NPcomplete 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
.
 References:
 NPcomplete and NPHard?
 From: yijun_lily
 Re: NPcomplete and NPHard?
 From: Torben Ægidius Mogensen
 Re: NPcomplete and NPHard?
 From: Bart Demoen
 Re: NPcomplete and NPHard?
 From: JeanMarc Bourguet
 NPcomplete and NPHard?
 Prev by Date: Re: NPcomplete and NPHard?
 Next by Date: Re: F.Y.I.  Revised paper "P=NP: LP Formulation of the TSP"
 Previous by thread: Re: NPcomplete and NPHard?
 Next by thread: Re: NPcomplete and NPHard?
 Index(es):
Relevant Pages
