[Computational Complexity] Maybe He Missed Some Math
Thomas Garrity's book All the Mathematics You Missed [But Need to Know for Graduate School] has a section on P versus NP which says
The N in NP is somewhat of a joke; NP stands for "not polynomial".and later
While initially the smart money was on P ≠ NP, today increasingly the belief is that the statement P=NP is independent of the other axioms of mathematics. Few believe P=NP.For the record NP stands for "Nondeterministic Polynomial-Time" (not a joke) and at least this complexity theorist feels that a proof of P≠NP exists and we just haven't found it yet. Just because we are too stupid to find the proof doesn't mean the problem is independent.
I don't mean to be hard on Garrity. He should be lauded for including the P versus NP problem in his book.
Thanks to Varsha Dani for the pointer.
Posted by Lance to Computational Complexity at 2/9/2005 04:40:58 PM