Earlier quoted context omitted.
But, there was no prize for solving FLT other than being able to list on one's CV "Proved FLT."
You wouldnt actually need to put that in your CV
You actually won't need a CV.
P ≠ NP
201–210 of 233 posts
Re: P ≠ NP
#202I think there might be a way to solve all n-SAT problems (if reformulated using conjunctive normal form) in O(C) best up to worst O(C * N * N) time and O(C * N) space (C = number of AND-clauses, N = number of distinct literals from all clauses). would that still be polynomial and a valid proof or even possible (not a mathematician I am)? on the other hand, proving P = NP would not be wise, morally seen, would it?
Re: P ≠ NP
#203Earlier quoted context omitted.
I didn't follow everything in my complexity class, but I believe that P=NP implies that search is as easy as decision. So producing a piece of good music is as easy (up to a polynomial) as deciding if a piece of music is good. If I remember correctly, optimization also collapses. So finding the best possible piece of music is also easy as deciding if a piece of music is good.
Up to a polynomial . What if the polynomial is of order 1000 or higher? I understand asymptotics and the convention that polynomial algorithms are "efficient". However, it might turn out that P=NP but the polynomial is so big that the found algorithm is impractical for normal sized instances.
That's certainly a logical possibility. In practice, low-degree polynomial solutions have been developed for most important problems in P, even if the first known polynomial solution had a high degree.
Re: P ≠ NP
#204Very interesting approach! How cool if this is the real deal. The last 30 years has seen a lot of theoretical work on computation as a physical process. If the greatest conjecture in CS is proved using tools from physics it really brings together math, physics, and CS. Edit: As someone else pointed out a few minutes ago http://www.hpl.hp.com/personal/Vinay_Deolalikar/ confirmations began arriving today. How soon befo…
Wrong area for a Nobel prize, the prize areas are physics, chemistry, physiology/medicine, literature, and peace. There is also a prize in economics given at the same time.
They'll give a peace prize for anything. Why not a proof of P!=NP?
Re: P ≠ NP
#205Earlier quoted context omitted.
I'm not sure whether Knuth has the ergodic-theory background. Perhaps call Terry Tao?
Tao comments on it (very briefly) here: http://terrytao.wordpress.com/2009/08/01/pnp-relativisation-...
Thanks for the info. I originally posted my request (half serious, half jokingly) when not many explanations in the thread were there to respond to the validity of the paper. Thanks for your insight.
Re: P ≠ NP
#206* RSA and all our other current crypto algorithms breathe a collective sigh of relief
Re: P ≠ NP
#207Earlier quoted context omitted.
I didn't follow everything in my complexity class, but I believe that P=NP implies that search is as easy as decision. So producing a piece of good music is as easy (up to a polynomial) as deciding if a piece of music is good. If I remember correctly, optimization also collapses. So finding the best possible piece of music is also easy as deciding if a piece of music is good.
Up to a polynomial . What if the polynomial is of order 1000 or higher? I understand asymptotics and the convention that polynomial algorithms are "efficient". However, it might turn out that P=NP but the polynomial is so big that the found algorithm is impractical for normal sized instances.
What would be even more entertaining, is a non-constructive proof of NP=P.
Re: P ≠ NP
#208His personal home page http://www.hpl.hp.com/personal/Vinay_Deolalikar/ seems to have been updated. "Manuscript sent on 6th August to several leading researchers in various areas. Confirmations began arriving 8th August early morning. Final version of the paper to be posted here shortly. Stay tuned. "
It's been updated again, with a revised version of the draft ("minor updates") dated August 9, 2010.
Re: P ≠ NP
#209Wow. 100% of zac’s 724 karma points come from this post & his comments on it.
Re: P ≠ NP
#210102 pages via one of the most annoying PDF readers on the planet? No thanks. There are good, free, PDF readers for every major operating system and for every major mobile device. I wish people would just link directly to PDFs.
+1 to that. Is there any point to Scribd other than putting ads on PDFs?