X-Message-Number: 8628
Date: Fri, 26 Sep 1997 12:20:24 -0400
From: "John P. Pietrzak" <>
Subject: Re: Smoking Rope
References: <>

Peter Merel wrote:
> Whoops, I meant NP-complete, not NP. P is a subset of NP, with
> NP-complete being its complement. Sorry, it's been a while ...

Quick note: it's even worse than that.  (For those in our viewing
audience who missed  Essentially, P is the set of
problems solvable in polynomial time on a deterministic Turing Machine,
and NP is the set of problems solvable in polynomial time on a
nondeterministic Turing Machine.  NP-complete problems have the
unique property that (1) they belong to the class of problems which
can be solved on a NDTM in polynomial time, and more interestingly,
(2) there is a polynomial-time transformation from *all* other problems
in NP to this one (i.e., if you can solve this problem in polynomial
time, you can solve all of them).

We know that all the problems in P are in NP.  Unfortunately, we don't
know whether the NP-complete problems are a complement of P within NP
or not; for all we know, all the problems in NP may even be in P.

As for the rest of the posting, I agree totally. :)


John

P.S.  This posting brought to you in part by "Computers and
Intractability", Garey & Johnson, W.H Freeman & co., 1979.  A very
good book on the subject.

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=8628