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
