1
edit
Changes
Jump to navigation
Jump to search
Line 40:
Line 40: + + + +
→NP Complete: new section
==Why Mathematicians Prefer the Alternative Definition==
==Why Mathematicians Prefer the Alternative Definition==
Because mathematician make a distinction between irreducible elements (p irred. <=> (a|p => a unit or a=p)) and prime elements (p prime <=> (for all a,b: p|ab => p|a or p|b). While these two properties coincide on <math>\mathbf{Z}</math>, they differ e.g., on <math>\mathbf{Z}[\sqrt{-5}]</math>: here 3 is irreducible, but not a prime, as <math>21 = 3 \cdot 7 = (1 + 2 \sqrt{-5})(1 - 2 \sqrt{-5})</math> --[[User:DiEb|DiEb]] 13:03, 29 August 2008 (EDT)
Because mathematician make a distinction between irreducible elements (p irred. <=> (a|p => a unit or a=p)) and prime elements (p prime <=> (for all a,b: p|ab => p|a or p|b). While these two properties coincide on <math>\mathbf{Z}</math>, they differ e.g., on <math>\mathbf{Z}[\sqrt{-5}]</math>: here 3 is irreducible, but not a prime, as <math>21 = 3 \cdot 7 = (1 + 2 \sqrt{-5})(1 - 2 \sqrt{-5})</math> --[[User:DiEb|DiEb]] 13:03, 29 August 2008 (EDT)
== NP Complete ==
Please fix the incorrect statement about the NP-completeness of prime factorization. In fact, prime factorization is ''known'' not to be in NPC unless P=NP. --[[User:DiogenesTonne|DiogenesTonne]] 17:59, 22 April 2009 (EDT)