From: jhnieto@luz.ve Subject: Re: Difference between NP, NP-complete and NP-hard Date: Sun, 02 Nov 1997 16:21:47 -0600 Newsgroups: sci.math In article <345C3F66.7684@ix.netcom.com>, Couris wrote: > > David Golding wrote: > > > > In my third year computer science course I have encountered NP, > > NP-complete and NP-hard problems. What an NP problem is has been defined > > for us (that an NP problem is solvable in polynomial time by a > > non-deterministic machine). NP-complete has been defined as the > > intersect of the sets of NP problems and NP-hard problems. We have been > > given examples of NP-comple and NP-hard problems (Travelling Salesman, > > 3-SAT) but we don't see how these are defined as such. > > > > I would be very grateful for an explanation of what NP-complete and > > NP-hard problems actually are. [snip] > I always thought NP-complete meant that there did not exist a > polynomial-time algorithm for the given problem. NP means non- > polynomial. That is, it is a complete(finished) problem as to > finding a polyn-time algor. for the problem. One does not exist. No, NP does not mean "non-polynomial" but "Non-deterministic Polynomial". Informally, P stands for the class of decision problems (i.e. problems whose answer is Yes or No) solvable in polinomially bounded time by deterministic machines. NP stands for the class of decision problems solvable by non-deterministic machines in polinomially bounded time. I'll not try to define precisely in what sense a decision problem is "solved" by a non-deterministic machine, but one might say that this happens if the machine "with luck" (i.e. taking appropriate random decisions) can find the correct answer. Well, since deterministic machines are a subset of non-deterministic machines, P is contained in NP. We don't know if the inclusion is proper or if P = NP. However in 1971 S.A. Cook proved that a particular NP problem known as SAT (Satisfiability of sets of boolean clauses) has the property that, if it is solvable in polinomial time, so are all NP problems. This is what is called a "NP-complete" problem: a NP problem such that, if it is in P, then NP = P. If a (not necessarily NP) problem has this same property then it is called "NP-hard". Thus the class of NP-complete problems is the intersection of the NP and NP-hard classes. For a more precise and formal account you should consult a good text, such as Garey & Johnson "Computers and Intractability" (W.H. Freeman). Available in the web is "Algorithms and Complexity" by Herbert Wilf, at http://www.cis.upenn.edu/~wilf/AlgComp.html José H. Nieto ============================================================================== From: orjanjo@lie.matstat.unit.no (Orjan Johansen) Newsgroups: sci.math Subject: Re: Difference between NP, NP-complete and NP-hard Date: 4 Nov 1997 15:13:30 GMT In article <878509007.22615@dejanews.com>, wrote: >However >in 1971 S.A. Cook proved that a particular NP problem known as SAT >(Satisfiability of sets of boolean clauses) has the property that, >if it is solvable in polinomial time, so are all NP problems. This is >what is called a "NP-complete" problem: a NP problem such that, if it >is in P, then NP = P. NP-complete problems have the property that every other NP problem can be _reduced_ to them (in polynomial time.) However, there might still be problems that are too hard to be in P, but still not powerful enough that everything else in NP can be reduced to them. I vaguely recall that it has proven that if P != NP, then there are problems that are neither in P nor NP-complete. I also recall that factorization of integers is believed to be such a problem, although I'm not sure if that has been proved (on the condition P != NP.) Greetings, Ørjan. -- (Éæ ùïõ ãáî òåáä ôèéó¬ ùïõ áòå îïô åéçèô âéô ãìåáî®) Finally, I propose that Cyberpromo and Agis be destroyed. =============================================================================== From: jhnieto@luz.ve Subject: Re: Difference between NP, NP-complete and NP-hard Date: Tue, 04 Nov 1997 16:55:18 -0600 Newsgroups: sci.math In article <63ne2q$8g8$1@due.unit.no>, orjanjo@lie.matstat.unit.no (Orjan Johansen) wrote: > > In article <878509007.22615@dejanews.com>, wrote: > >However > >in 1971 S.A. Cook proved that a particular NP problem known as SAT > >(Satisfiability of sets of boolean clauses) has the property that, > >if it is solvable in polinomial time, so are all NP problems. This is > >what is called a "NP-complete" problem: a NP problem such that, if it > >is in P, then NP = P. > > NP-complete problems have the property that every other NP problem can > be _reduced_ to them (in polynomial time.) However, there might still > be problems that are too hard to be in P, but still not powerful > enough that everything else in NP can be reduced to them. > > I vaguely recall that it has proven that if P != NP, then there are > problems that are neither in P nor NP-complete. I also recall that > factorization of integers is believed to be such a problem, although > I'm not sure if that has been proved (on the condition P != NP.) You are right. In my post I was just trying to convey informally and with a few words the meaning of P, NP and NP-complete, avoiding the definition of polynomial reducibility. The "intermediate" problems that you mention (class NPI) necessarily exist if P != NP. This follows from results proved by Ladner around 1975. However the examples are too complicated and unnatural (they are constructed using diagonalization techniques, etc.) "Natural" candidates to be in NPI (assuming that P != NP) were the "composite numbers" and "graph isomorphism" problems, but I don't know if either of them has been proved to be or not to be in NPI. José H. Nieto ============================================================================= Newsgroups: sci.math From: christian.bau@isltd.insignia.com (Christian Bau) Subject: Re: NP-complete and NP-hard Date: Thu, 19 Feb 1998 09:32:38 GMT In article <6cg3nu$mbl$1@nnrp1.dejanews.com>, nagendra@sasi.com wrote: > Hi all, > > I would greatly appreciate if any one of you can explain the > exact difference between the terms 'NP-complete' and 'NP-hard'. Very roughly: A problem is in the class NP, if you can check a guess for a solution in polynomial time. For example, take the three coloring problem: If I give you any planar graph, can you color it with three colors? Doing this is very hard, but checking that a coloring does indeed consist of three colors is very simple. A problem X is NP-hard if it is hard enough that every problem in NP can be solved in polynomial time _if_ you only could solve problem X in polynomial time. But this includes problems that are much harder than problems in NP. A problem X is NP-complete if it is hard enough to be NP-hard, but still easy enough to be in NP. This means that all NP-complete problems are roughly equally hard to solve.