Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This question already has an answer here:

I have read that TSP and Subset Sum problems are NPC problems which are also NP Hard. There are also problems like Halting Problem which is NP Hard, but not NP Complete

And Wikipedia defines this as

A problem $H$ is NP-hard if and only if there is an NP-complete problem $L$ that is polynomial time Turing-reducible to $H$.

Like NP Complete problem is there any problem considered to be the first NP Hard problem?

To show one problem to be NP Hard we need just to reduce one NPC problem to it?

Whether all NPC problems are NP Hard?

If no, why not?

share|improve this question

marked as duplicate by Raphael Mar 26 at 18:02

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

add comment

2 Answers 2

up vote 6 down vote accepted

A problem is NP-hard if every problem in NP can be reduced to it by some appropriate kind of reductions (typically, polynomial-time many-one reductions). A problem is NP-complete if it is in NP and is NP-hard.

Therefore, by definition, every NP-complete problem is NP-hard.

share|improve this answer
add comment

A problem is NP-complete if (1) it belongs to NP, and (2) if every problem in NP can be reduced to it in polynomial time. If (2) holds, a problem is said to be NP-hard. In other words, we say a problem is NP-complete if it is both NP-hard and in NP.

Polynomial-time reducibility is a relation among languages, and it is also transitive. That is to say, yes, you can prove NP-hardness of a problem by reducing a problem of known hardness to a problem of unknown hardness. For example, you could reduce 3-SAT to your new problem X, and it would prove X is NP-hard. Additionally, if you show X is also in NP, you have that X is NP-complete.

You might want to take a look at the Cook-Levin Theorem. By the theorem, we know that SAT and 3-SAT are NP-complete. Some of the "first" NP-complete problems were given by Karp.

share|improve this answer
    
My question is about NP Hard, not about NP Complete –  user5507 Mar 26 at 15:56
    
My answer is about NP-hardness. –  Juho Mar 26 at 16:52
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.