What are the differences between NP NP-Complete and NP-Hard

Question

What are the differences between NP  NP-Complete and NP-Hard   I am aware of many resources all over the web  I d like to read your explanations  and the reason is they might be different from what s out there  or there is something that I m not aware of

User · Answer

NP-complete problems are those problems that are both NP-Hard and in the complexity class NP. Therefore, to show that any given problem is NP-complete, you need to show that the problem is both in NP and that it is NP-hard.

Problems that are in the NP complexity class can be solved non-deterministically in polynomial time and a possible solution (i.e., a certificate) for a problem in NP can be verified for correctness in polynomial time.

An example of a non-deterministic solution to the k-clique problem would be something like:

1) randomly select k nodes from a graph

2) verify that these k nodes form a clique.

The above strategy is polynomial in the size of the input graph and therefore the k-clique problem is in NP.

Note that all problems deterministically solvable in polynomial time are also in NP.

Showing that a problem is NP-hard typically involves a reduction from some other NP-hard problem to your problem using a polynomial time mapping: http://en.wikipedia.org/wiki/Reduction_(complexity)

User · Answer

This is a very informal answer to the question asked   Can 3233 be written as the product of two other numbers bigger than 1   Is there any way to walk a path around all of the Seven Bridges of K  nigsberg without taking any bridge twice   These are examples of questions that share a common trait   It may not be obvious how to efficiently determine the answer  but if the answer is  yes   then there s a short and quick to check proof   In the first case a non-trivial factorization of 51  in the second  a route for walking the bridges  fitting the constraints    A decision problem is a collection of questions with yes or no answers that vary only in one parameter   Say the problem COMPOSITE   Is n composite   n is an integer   or EULERPATH   Does the graph G have an Euler path    G is a finite graph    Now  some decision problems lend themselves to efficient  if not obvious algorithms   Euler discovered an efficient algorithm for problems like the  Seven Bridges of K  nigsberg  over 250 years ago     On the other hand  for many decision problems  it s not obvious how to get the answer -- but if you know some additional piece of information  it s obvious how to go about proving you ve got the answer right   COMPOSITE is like this   Trial division is the obvious algorithm  and it s slow  to factor a 10 digit number  you have to try something like 100 000 possible divisors   But if  for example  somebody told you that 61 is a divisor of 3233  simple long division is a efficient way to see that they re correct   The complexity class NP is the class of decision problems where the  yes  answers have short to state  quick to check proofs   Like COMPOSITE   One important point is that this definition doesn t say anything about how hard the problem is   If you have a correct  efficient way to solve a decision problem  just writing down the steps in the solution is proof enough   Algorithms research continues  and new clever algorithms are created all the time   A problem you might not know how to solve efficiently today may turn out to have an efficient  if not obvious  solution tomorrow   In fact  it took researchers until 2002 to find an efficient solution to COMPOSITE   With all these advances  one really has to wonder  Is this bit about having short proofs just an illusion   Maybe every decision problem that lends itself to efficient proofs has an efficient solution   Nobody knows   Perhaps the biggest contribution to this field came with the discovery a peculiar class of NP problems   By playing around with circuit models for computation  Stephen Cook found a decision problem of the NP variety that was provably as hard or harder than every other NP problem   An efficient solution for the boolean satisfiability problem could be used to create an efficient solution to any other problem in NP   Soon after  Richard Karp showed that a number of other decision problems could serve the same purpose   These problems  in a sense the  hardest  problems in NP  became known as NP-complete problems   Of course  NP is only a class of decision problems   Many problems aren t naturally stated in this manner    find the factors of N    find the shortest path in the graph G that visits every vertex    give a set of variable assignments that makes the following boolean expression true    Though one may informally talk about some such problems being  in NP   technically that doesn t make much sense -- they re not decision problems   Some of these problems might even have the same sort of power as an NP-complete problem  an efficient solution to these  non-decision  problems would lead directly to an efficient solution to any NP problem   A problem like this is called NP-hard

User · Answer

As I understand it  an np-hard problem is not  quot harder quot  than an np-complete problem   In fact  by definition  every np-complete problem is   in NP np-hard    -- Intro  to Algorithms  3ed  by Cormen  Leiserson  Rivest  and Stein  pg 1069

User · Answer

In addition to the other great answers  here is the typical schema people use to show the difference between NP  NP-Complete  and NP-Hard

User · Answer

There are really nice answers for this particular question  so there is no point to write my own explanation  So I will try to contribute with an excellent resource about different classes of computational complexity   For someone who thinks that computational complexity is only about P and NP  here is the most exhaustive resource about different computational complexity problems  Apart from problems asked by OP  it listed approximately 500 different classes of computational problems with nice descriptions and also the list of fundamental research papers which describe the class

User · Answer

P  Polynomial Time   As name itself suggests  these are the problems which can be solved in polynomial time  NP  Non-deterministic-polynomial Time   These are the decision problems which can be verified in polynomial time  That means  if I claim that there is a polynomial time solution for a particular problem  you ask me to prove it  Then  I will give  you a proof which you can easily verify in polynomial time  These kind of problems are called NP problems  Note that  here we are not talking about whether there is a polynomial time solution for this problem or not  But we are talking about verifying the solution to a given problem in polynomial time  NP-Hard   These are at least as hard as the hardest problems in NP  If we can solve these problems in polynomial time  we can solve any NP problem that can possibly exist  Note that these problems are not necessarily NP problems  That means  we may may-not verify the solution to these problems in polynomial time  NP-Complete  These are the problems which are both NP and NP-Hard  That means  if we can solve these problems  we can solve any other NP problem and the solutions to these problems can be verified in polynomial time

User · Answer

I think we can answer it much more succinctly  I answered a related question  and copying my answer from there  But first  an NP-hard problem is a problem for which we cannot prove that a polynomial time solution exists  NP-hardness of some  problem-P  is usually proven by converting an already proven NP-hard problem to the  problem-P  in polynomial time      To answer the rest of question  you first need to understand which NP-hard problems are also NP-complete  If an NP-hard problem belongs to set NP  then it is NP-complete  To belong to set NP  a problem needs to be       i  a decision problem      ii  the number of solutions to the problem should be finite and each solution should be of polynomial length  and     iii  given a polynomial length solution  we should be able to say whether the answer to the problem is yes no      Now  it is easy to see that there could be many NP-hard problems that do not belong to set NP and are harder to solve  As an intuitive example  the optimization-version of traveling salesman where we need to find an actual schedule is harder than the decision-version of traveling salesman where we just need to determine whether a schedule with length  lt   k exists or not

User · Answer

Find some interesting defintion

User · Answer

I ve been looking around and seeing many long explanations   Here is a small chart that may be useful to summarise   Notice how difficulty increases top to bottom  any NP can be reduced to NP-Complete  and any NP-Complete can be reduced to NP-Hard  all in P  polynomial  time    If you can solve a more difficult class of problem in P time  that will mean you found how to solve all easier problems in P time  for example  proving P   NP  if you figure out how to solve any NP-Complete problem in P time                                                                    Problem Type   Verifiable in P time   Solvable in P time   Increasing Difficulty                                                                            P                     Yes                    Yes                         NP                    Yes                 Yes or No                      NP-Complete           Yes                  Unknown                       NP-Hard            Yes or No               Unknown                                                                                            V   Notes on Yes or No entries      An NP problem that is also P is solvable in P time     An NP-Hard problem that is also NP-Complete is verifiable in P time      NP-Complete problems  all of which form a subset of NP-hard  might be  The rest of NP hard is not    I also found this diagram quite useful in seeing how all these types correspond to each other  pay more attention to the left half of the diagram

User · Answer

The easiest way to explain P v  NP and such without getting into technicalities is to compare  word problems  with  multiple choice problems    When you are trying to solve a  word problem  you have to find the solution from scratch  When you are trying to solve a  multiple choice problems  you have a choice  either solve it as you would a  word problem   or try to plug in each of the answers given to you  and pick the candidate answer that fits   It often happens that a  multiple choice problem  is much easier than the corresponding  word problem   substituting the candidate answers and checking whether they fit may require significantly less effort than finding the right answer from scratch   Now  if we would agree the effort that takes polynomial time  easy  then the class P would consist of  easy word problems   and the class NP would consist of  easy multiple choice problems    The essence of P v  NP is the question   Are there any easy multiple choice problems that are not easy as word problems   That is  are there problems for which it s easy to verify the validity of a given answer but finding that answer from scratch is difficult   Now that we understand intuitively what NP is  we have to challenge our intuition  It turns out that there are  multiple choice problems  that  in some sense  are hardest of them all  if one would find a solution to one of those  hardest of them all  problems one would be able to find a solution to ALL NP problems  When Cook discovered this 40 years ago it came as a complete surprise  These  hardest of them all  problems are known as NP-hard  If you find a  word problem solution  to one of them you would automatically find a  word problem solution  to each and every  easy multiple choice problem    Finally  NP-complete problems are those that are simultaneously NP and NP-hard  Following our analogy  they are simultaneously  easy as multiple choice problems  and  the hardest of them all as word problems

User · Answer

I assume that you are looking for intuitive definitions  since the technical definitions require quite some time to understand  First of all  let s remember a preliminary needed concept to understand those definitions    Decision problem  A problem with a yes or no answer      Now  let us define those complexity classes   P  P is a complexity class that represents the set of all decision problems that can be solved in polynomial time   That is  given an instance of the problem  the answer yes or no can be decided in polynomial time   Example  Given a connected graph G  can its vertices be coloured using two colours so that no edge is monochromatic   Algorithm  start with an arbitrary vertex  color it red and all of its neighbours blue and continue  Stop when you run out of vertices or you are forced to make an edge have both of its endpoints be the same color     NP  NP is a complexity class that represents the set of all decision problems for which the instances where the answer is  yes  have proofs that can be verified in polynomial time   This means that if someone gives us an instance of the problem and a certificate  sometimes called a witness  to the answer being yes  we can check that it is correct in polynomial time   Example  Integer factorisation is in NP  This is the problem that given integers n and m  is there an integer f with 1  lt  f  lt  m  such that f divides n  f is a small factor of n     This is a decision problem because the answers are yes or no  If someone hands us an instance of the problem  so they hand us integers n and m  and an integer f with 1  lt  f  lt  m  and claim that f is a factor of n  the certificate   we can check the answer in polynomial time by performing the division n   f     NP-Complete  NP-Complete is a complexity class which represents the set of all problems X in NP for which it is possible to reduce any other NP problem Y to X in polynomial time   Intuitively this means that we can solve Y quickly if we know how to solve X quickly  Precisely  Y is reducible to X  if there is a polynomial time algorithm f to transform instances y of Y to instances x   f y  of X in polynomial time  with the property that the answer to y is yes  if and only if the answer to f y  is yes   Example   3-SAT  This is the problem wherein we are given a conjunction  ANDs  of 3-clause disjunctions  ORs   statements of the form   x v11 OR x v21 OR x v31  AND   x v12 OR x v22 OR x v32  AND                            AND   x v1n OR x v2n OR x v3n    where each x vij is a boolean variable or the negation of a variable from a finite predefined list  x 1  x 2      x n     It can be shown that every NP problem can be reduced to 3-SAT  The proof of this is technical and requires use of the technical definition of NP  based on non-deterministic Turing machines   This is known as Cook s theorem   What makes NP-complete problems important is that if a deterministic polynomial time algorithm can be found to solve one of them  every NP problem is solvable in polynomial time  one problem to rule them all      NP-hard  Intuitively  these are the problems that are at least as hard as the NP-complete problems  Note that NP-hard problems do not have to be in NP  and they do not have to be decision problems    The precise definition here is that a problem X is NP-hard  if there is an NP-complete problem Y  such that Y is reducible to X in polynomial time   But since any NP-complete problem can be reduced to any other NP-complete problem in polynomial time  all NP-complete problems can be reduced to any NP-hard problem in polynomial time  Then  if there is a solution to one NP-hard problem in polynomial time  there is a solution to all NP problems in polynomial time   Example  The halting problem is an NP-hard problem  This is the problem that given a program P and input I  will it halt  This is a decision problem but it is not in NP  It is clear that any NP-complete problem can be reduced to this one  As another example  any NP-complete problem is NP-hard   My favorite NP-complete problem is the Minesweeper problem     P   NP  This one is the most famous problem in computer science  and one of the most important outstanding questions in the mathematical sciences  In fact  the Clay Institute is offering one million dollars for a solution to the problem  Stephen Cook s writeup on the Clay website is quite good     It s clear that P is a subset of NP  The open question is whether or not NP problems have deterministic polynomial time solutions  It is largely believed that they do not  Here is an outstanding recent article on the latest  and the importance  of the P   NP problem  The Status of the P versus NP problem    The best book on the subject is Computers and Intractability by Garey and Johnson

[computer-science] What are the differences between NP, NP-Complete and NP-Hard?

Examples related to computer-science

Examples related to complexity-theory

Examples related to np

Examples related to np-complete

Examples related to np-hard