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.
(From Garey and Johnson so you probably know this.)
ReplyDeleteOne proposed name for NP was PET.
For NOW it stands for Probably exponetial time
if P\ne NP then it stands for Provably exponential time
(unless NP is n^{log n} or something like that)
if P=Np then its Previously exponential time.
As for people thinking that P vs NP is ind of stuff,
in a survey I did a while back (its in SIGACT NEWS)
of 100 theorists only 3 thought it was independent.
And one of them emailed me later that he didn't really
think that, but thought it would be a cool way to vote.
So Garrity is PROVABLY wrong
Perhaps a naive question -- if P=NP is shown to be independent of other axioms, what does that say about our ability to solve an NP-complete problem in polynomial time?
ReplyDeleteNot such a naive question and no short answer. Check out this survey by Aaronson.
ReplyDeleteHow is the rest of the book? Is it worth recommending?
ReplyDelete(Perhaps you should drop the author a line, so it could at least appear in errata.)
From what I could tell, the rest of the book is a pretty comprehensible - but a very, very brief- review of most of the mathematics one might need for a grad school. It cannot serve as a textbook of any sort - rather as a coarse intro. For me the chapter on P vs NP (for all its mistakes) actually worked: I was so surprised to learn that there is a possibility that P vs NP is independent, that I Googled it right away and the first result was, naturally, Scott's paper - great reading!
ReplyDeletePeter
Thanks Scott, interesting article
ReplyDelete