Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

NP-hard or NP-Complete

  1. Nov 14, 2006 #1
    I have a question. Is the class of problems NP-Complete more difficult to solve than the class of problems NP-Hard?

    I mean, NP-Complete problems are in NP, and also are NP-Hard, but not all NP-Hard problems are in NP... How to tell which one is more difficult to solve?
  2. jcsd
  3. Nov 14, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    The set of problems that are NP-hard is a strict superset of the problems that are NP-complete. Some problems (like the halting problem) are NP-hard, but not in NP.
  4. Nov 14, 2006 #3


    User Avatar
    Science Advisor
    Homework Helper

    NP-Hard problems that are not NP-Complete are 'harder' than NP problems, in general, in that they take up more computational resources of some type: memory, time, alternation, randomness, etc.
  5. Nov 14, 2006 #4


    User Avatar
    Science Advisor

    Or as Nate mentioned, NP-hard problems might be impossible to solve in general. You can tell the difference in difficulty between NP-hard and NP-complete problems because the class NP includes everything easier than its "toughest" problems--if a problem is not in NP, it is harder than all the problems in NP.

    By the way, would you post things like this in the future in the Programming forum, as it is a computer science question?
    Last edited: Nov 14, 2006
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook