# Re: NP-complete and NP-Hard?

*From*: djimenez@xxxxxxxxxxxxx (Daniel A. Jimenez)*Date*: 21 Jun 2005 09:28:52 -0500

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

.

**References**:**NP-complete and NP-Hard?***From:*yijun_lily

**Re: NP-complete and NP-Hard?***From:*Torben Ægidius Mogensen

**Re: NP-complete and NP-Hard?***From:*Bart Demoen

**Re: NP-complete and NP-Hard?***From:*Jean-Marc Bourguet

- Prev by Date:
**Re: NP-complete and NP-Hard?** - Next by Date:
**Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"** - Previous by thread:
**Re: NP-complete and NP-Hard?** - Next by thread:
**Re: NP-complete and NP-Hard?** - Index(es):