Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Can someone please summarize the exact difference between NP-Complete and NP-Hard problems in simple language? Wiki and my standard books aren't exactly helping.

share|improve this question

closed as too localized by Aaron Roth, Kaveh, Tsuyoshi Ito, Noam, Daniel Apon Oct 9 '10 at 17:38

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

3  
too elementary (defined very well on wiki and in any decent introduction to complexity book), voting to close. –  Kaveh Oct 9 '10 at 17:20
2  
To voters: when you vote to close as too elementary, please consider to use “too localized” instead of “off topic” as a reason. –  Tsuyoshi Ito Oct 9 '10 at 17:30
1  
@chronoz, I would highly recommend reading the site's FAQ if you have any questions about why this question was closed, especially this and this. –  Daniel Apon Oct 9 '10 at 17:42

1 Answer 1

A NP-complete problem is an NP-hard problem which is in NP.

share|improve this answer
    
Figured I'd slip in a quick comment, in case it helps the OP, before the question is closed for being too elementary: Monoid's answer is the correct definition. Some further, natural implications: Any problem harder than an NP-complete problem is NP-hard; NP-complete problems are NP-hard; any problem easier than an NP-complete problem is not NP-hard. –  Daniel Apon Oct 9 '10 at 17:38