Computational Complexity

Wednesday, February 09, 2005

 
Maybe He Missed Some Math

Posted by Lance

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.

4:40 PM # 8 comments

1.  GASARCH says:  
   
   (From Garey and Johnson so you probably know this.)
   One 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
   

   6:35 PM, February 09, 2005

2.  Yaroslav says:  
   
   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?
   

   8:13 PM, February 09, 2005

3.  Lance says:  
   
   Not such a naive question and no short answer. Check out this survey by Aaronson.
   

   8:32 PM, February 09, 2005

4.  Macneil says:  
   
   How is the rest of the book? Is it worth recommending?
   
   (Perhaps you should drop the author a line, so it could at least appear in errata.)
   

   8:55 AM, February 10, 2005

5.  Scott says:  
   
   Yaroslav: since I don't think I said this explicitly in the survey, it means that either P!=NP but there's no proof in the given axiom system, or that there's a polynomial-time algorithm for SAT but no proof of its correctness.
   

   12:12 AM, February 12, 2005

6.  Scott says:  
   
   This post has been removed by a blog administrator.
   

   12:13 AM, February 12, 2005

7.  Anonymous says:  
   
   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!
   Peter
   

   10:42 AM, February 12, 2005

8.  Yaroslav says:  
   
   Thanks Scott, interesting article
   

   4:59 PM, February 26, 2005

Comment Feeds: This Post All