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". 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
