In comp.theory Wim Benthem <email@example.com> wrote: > On Tue, 25 Oct 2005 18:05:06 +0000 (UTC), firstname.lastname@example.org wrote:
>>No, NP-Complete means that the problem is in NP and it is >>NP-hard. You can prove a problem is NP-hard by reducing >>it to another NP-hard problem. There is no need to use >>an NP-complete problem to show that a problem is NP-hard. >>
> You prove a problem is NP-hard by reducing another NP-hard > problem to it. Everything in NP can be reduced to > any NP-hard problem by definition. Nothing to prove there.
Yes, I said that backwards. My point was that you do not need to use an NP-complete problem to prove that a problem is NP-hard. You just need to reduce a known NP-hard problem to your new problem.