That's funny -- I just spent 5 days on holiday with my old friend Neil Immerman, who won the Godel Prize in 1995 for proving NL = co-NL,. I don't think that he mentioned the P=NP thing once. And then I get back online and find that sage-devel is buzzing with it!
John On Aug 11, 3:10 am, Bill Hart <goodwillh...@googlemail.com> wrote: > On 10 Aug, 19:12, Nils Bruin <nbr...@sfu.ca> wrote: > > > On Aug 10, 10:29 am, Bill Hart <goodwillh...@googlemail.com> wrote: > > > > Just in case this is being missed here, a problem is by definition in > > > NP only if it has been shown equivalent to one of the other NP- > > > complete problems. > > > I assume that with "equivalent" you mean "polynomially equivalent". > > Yes, I screwed up the definition. Thanks for the correction. > > > > > With your definition, P subset NP implies P=NP. > > > I think it's more usual to define P and NP first, then prove that P is > > a subset of NP and then prove that there actually are NP problems to > > which any other NP problem can be reduced in polynomial time, and call > > those problems NP-complete. A priori, there is plenty of room in NP > > for non-NP-complete problems (should Deolalikar be right, any problem > > in P would do). > > > Which makes me wonder: Is any problem in P also P-complete? Can any > > polynomial problem be reduced to "solve x=0" in polynomial time? -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
