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