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.