Results 1 to 12 of 12

Math Help - difference between np complete and np hard

  1. #1
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292

    Lightbulb difference between np complete and np hard

    greetings!!!
    could anybody tell me the difference between np hard and np complete (in simple way). I have read articles on many sites but they are a bit complex.
    now this is what I think
    np complete problems are those problems whose solution can be verified in polynomial time by a non deterministic turing machine.
    np hard problems are the hardest problems whose solution might not be verifiable.
    please do correct me if i am wrong.
    also a problem is np hard if there exist np complete problem that is reducible to np harp problem

    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    np complete problems are those problems whose solution can be verified in polynomial time by a non deterministic turing machine.
    No. First, either a solution has to be found by a nondeterministic TM or a solution and a proof that it is indeed a solution have to be verified by a deterministic TM. (Both variants have to be done in polynomial time.) And then such problem is called to be in NP, not NP-complete.

    np hard problems are the hardest problems whose solution might not be verifiable.
    Usually one deals with decidable problems when talking about NP-complete, NP-hard, etc. Thus, solutions to such problems can not only be verified, but also found.

    also a problem is np hard if there exist np complete problem that is reducible to np harp problem
    Yes. This can be taken as a definition.

    Basically, a problem P is called NP-hard if every problem in NP is polynomial-time reducible to P. A problem is called NP-complete if it is NP-hard and it itself is in NP. Thus, NP-hard problems can be harder than NP-complete ones.

    The Wikipedia article describes this pretty well.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292
    1) a np problem is the decision problem whose solution can be found in polynomial time by non deterministic TM and whose solution is verifiable in polynomial time by deterministic TM.
    2) a problem c is np complete problem if it is in np and every np problem is reducible to c in polynomial time
    3) a problem k is np hard if its at least as hard as hardest problem in np and there exist np complete problem which is polynomial time reducible to np hard.
    hope I am correct ( if am not then do tell me)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    1) a np problem is the decision problem whose solution can be found in polynomial time by non deterministic TM and whose solution is verifiable in polynomial time by deterministic TM.
    First, the two conditions joined by "and" are equivalent. It's not like you need both of them. Second, it is important to understand what "whose solution is verifiable in polynomial time" means. It's not that you have a deterministic TM such that you give a problem and a hypothetic answer, e.g., "yes", and it verifies whether the answer is correct. I don't have time at the moment to write the precise definition, but see it explained here.

    2) a problem c is np complete problem if it is in np and every np problem is reducible to c in polynomial time
    Yes.

    3) a problem k is np hard if its at least as hard as hardest problem in np and there exist np complete problem which is polynomial time reducible to k.
    Again, these two conditions are equivalent (roughly speaking); you only need one of them.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292
    is it true that all np complete problems are not reducible to np hard (such problems are in np)
    reason:-
    suppose there are 3 problems 1) A (which is np) 2) B (which is np complete) 3) C (which is np hard).
    now A is reducible to B (as every np problem is reducible to np complete) which is further reducible to C (np complete problem is reducible to np hard)or we may say A is reducible to C it means A is np and reducible to np hard problem and hence A should be np complete (which is contradictory to our assumption that a is np not np complete)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292
    will there be a new class (say super hard) if np hard problems are reducible to some single problem ( as np complete problems are reducible to np hard problems)
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    is it true that all np complete problems are not reducible to np hard (such problems are in np)
    All problems in NP (including NP-complete ones) are poly-time reducible to any NP-hard problem.

    it means A is np and reducible to np hard problem and hence A should be np complete
    It does not follow that A is NP-complete.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    will there be a new class (say super hard) if np hard problems are reducible to some single problem ( as np complete problems are reducible to np hard problems)
    As far as I know, there is an infinite hierarchy. \mathrm{NP}=\Sigma^p_1\subseteq\Sigma^p_2\subseteq  \dots (polynomial hierarchy). All these problems are decidable. Then there are semi-decidable problems, denoted by \Sigma^0_1, which are properly contained in \Sigma^0_2\subset\Sigma^0_3\subset\dots (arithmetic hierarchy).

    Of course, the hardest of all problems is the Ultimate Question of Life, the Universe, and Everything (and we already know the answer!).
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292
    so is it this way
    np problem:- problem that can be solved in polynomial time by non deterministic turing machine or whose solution can be found in polynomial time by deterministic turing machine.
    np complete:- a problem is np complete if every np problem is reducible to np complete in polynomial time.
    np hard:- problems at least as hard as np complete and there should exist np complete problem reducible to np hard.
    but how can we decide if a problem is only np or np complete or np hard???
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    np problem:- problem that can be solved in polynomial time by non deterministic turing machine
    Yes.

    or whose solution can be found in polynomial time by deterministic turing machine.
    No. In my opinion, to solve a problem is the same thing as to find its solution. Therefore, "problem that can be solved in polynomial time" (from the first quote) is the same thing as problems "whose solution can be found in polynomial time" (from the second quote); however, in the first quote you require nondeterministic machines while in the second quote you require deterministic ones. That's why, in my opinion, the second quote is incorrect.

    The important thing about the second variant is that together with a problem, one gives to a deterministic machine a polynomial-size proof, also called certificate, that the answer is "yes". The machine then verifies not just the answer "yes" but the fact that the proof is correct. The machine does not have to discover this proof; in fact, it can be discovered in polynomial time only by a nondeterministic machine. More formally (see this lecture from Brown University): A language (set of problem instances for which the answer is "yes") L is called to be in NP if there exist a polynomial p and a polynomial-time deterministic machine M such that for every problem instance x, x is in L iff there exists a proof y such that |y| <= p(|x|) and M(x,y) = "yes". (Here |x| and |y| are sizes of x and y, respectively.)

    np complete:- a problem is np complete if every np problem is reducible to np complete (which one?) in polynomial time.
    No, this is NP-hard. See the definition in post #2 above.

    np hard:- problems at least as hard as np complete and there should exist np complete problem reducible to np hard.
    These two conditions are equivalent.

    but how can we decide if a problem is only np or np complete or np hard???
    It may not be easy. You can show that a problem is in NP by definition. To show that a problem L is NP-complete you show that it is in NP and that another NP-complete problem (and therefore all problems in NP) is reducible to L. To show just that L is NP-hard you prove the second part only.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member nikhil's Avatar
    Joined
    Jun 2008
    Posts
    292

    Post

    Formal overview
    NP-complete is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a nondeterministic Turing machine. A problem p in NP is also in NPC if and only if every other problem in NP can be transformed into p in polynomial time. NP-complete can also be used as an adjective: problems in the class NP-complete are known as NP-complete problems.
    taken from wiki.
    so I guess every np problem is reducible to np complete and some np complete problem are reducible to np hard ( am i correct!!!)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    some np complete problem are reducible to np hard
    Every problem in NP (including NP-complete ones) is reducible to every NP-hard problem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: June 29th 2011, 05:57 PM
  2. complete or not ?
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: June 3rd 2010, 08:14 AM
  3. Replies: 2
    Last Post: February 28th 2010, 12:48 PM
  4. Complete Set
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: February 4th 2009, 03:17 AM
  5. difference between finite element/finite difference method
    Posted in the Advanced Applied Math Forum
    Replies: 0
    Last Post: October 2nd 2008, 11:03 AM

Search Tags


/mathhelpforum @mathhelpforum