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
.

Relevant Pages

  • Re: NP-hardness
    ... completeness proof (reduction from a known NP-complete decision problem ... NP-hard problem to it) and that it is NP. ... Optimization problem which is NP hard but not NP-complete like minimum ... We'll solve SAT by finding the minimum reprezentation of BF. ...
    (sci.math)
  • Re: Can someone give me an example of this type of problem?
    ... > I have seen the definition of NP-Complete as a problem that is both NP-Hard ... > and in NP and began wondering about problems that didn't fit this definition. ... is apparently harder than any NP-complete problem. ...
    (comp.theory)
  • Re: NP - Hard -- Approximation algos
    ... A NP-hard problem is a problem such that every problem in NP poly-time ... (NP-complete). ... route shorter than k for this graph!", ...
    (sci.crypt)
  • Re: NP-complete and NP-Hard?
    ... I though that NP-complete is the intersection of ... NP and NP-hard. ... Isn't this question equivalent to P ?= NP? ...
    (comp.theory)
  • Re: Discussion about transformation TSP to UniqueTSP
    ... Radoslaw Hofman wrote: ... presented as union of languages then some of them are NP-complete... ... "If Q is NP-Complete, and Q is Union of languages Q1...Qn, where each ... we will refer to it as the Deepak-Hofman-Bryan Theorem ...
    (comp.theory)