Calgarypuck Forums - The Unofficial Calgary Flames Fan Community
Old 08-09-2010, 12:05 PM   #1
BlackEleven
Redundant Minister of Redundancy
 
BlackEleven's Avatar
 
Join Date: Apr 2004
Location: Montreal
Exp:
Default P vs. NP problem solved?

This pretty nerdy, but it is the tech forum so I thought I'd give it a shot.

There's a proof that claim to have solved the P vs. NP problem, claiming that P != NP.

Here's a brief summary of the paper:
http://rjlipton.wordpress.com/2010/0...t-equal-to-np/

For those not familiar, this is pretty well the holy grail of theoretical computer science and a verified proof has Millenium Prize of $1M attached to it. This paper has not been peer-reviewed yet, but its generating a lot of buzz on the 'net.

If you need a refresher/explanation on the P vs. NP problem, wikipedia has a good page on it:
http://en.wikipedia.org/wiki/P_versus_NP_problem

Needless to say, if this paper is true, it has huge implications for computer science algorithms.

The paper, in its entirety (100 pages), can be found here:
http://www.scribd.com/doc/35539144/pnp12pt
BlackEleven is offline   Reply With Quote
Old 08-09-2010, 12:22 PM   #2
yads
Powerplay Quarterback
 
Join Date: Apr 2008
Exp:
Default

Crazy if it is indeed solved. Does it really have huge implications for computer science algorithms though? It has long been believed that P != NP. Now if it were shown that P == NP then that would have huge reprecussions, but I'm not sure it's anything, but business as usual as far as comptuting algorithms go.
yads is offline   Reply With Quote
Old 08-09-2010, 12:29 PM   #3
BlackEleven
Redundant Minister of Redundancy
 
BlackEleven's Avatar
 
Join Date: Apr 2004
Location: Montreal
Exp:
Default

Yes, P = NP would definitely have much bigger repercussions, but I imagine P != NP would be at least an assurance to anyone working in an area such a cryptography or security where the assumption is made there is no solution in polynomial time. But, yeah, P != NP is probably much more of a big deal in theoretical computer science than practical.
BlackEleven is offline   Reply With Quote
Old 08-09-2010, 12:55 PM   #4
photon
The new goggles also do nothing.
 
photon's Avatar
 
Join Date: Oct 2001
Location: Calgary
Exp:
Default

Fields Medal for sure if it's validated.
__________________
Uncertainty is an uncomfortable position.
But certainty is an absurd one.
photon is offline   Reply With Quote
Old 08-09-2010, 01:03 PM   #5
BlackEleven
Redundant Minister of Redundancy
 
BlackEleven's Avatar
 
Join Date: Apr 2004
Location: Montreal
Exp:
Default

Quote:
Originally Posted by photon View Post
Fields Medal for sure if it's validated.
Assuming he's under 40 years of age...
BlackEleven is offline   Reply With Quote
Old 08-09-2010, 01:09 PM   #6
photon
The new goggles also do nothing.
 
photon's Avatar
 
Join Date: Oct 2001
Location: Calgary
Exp:
Default

Quote:
Originally Posted by BlackEleven View Post
Assuming he's under 40 years of age...
Born in 1971, so just under.
__________________
Uncertainty is an uncomfortable position.
But certainty is an absurd one.
photon is offline   Reply With Quote
Old 08-10-2010, 06:13 AM   #7
Rathji
Franchise Player
 
Rathji's Avatar
 
Join Date: Nov 2006
Location: Supporting Urban Sprawl
Exp:
Default

NP complete problems were, by a very large margin, the favorite part of my Algorithms course.

I really am surprised to see it being solved though. Personally, I was hoping that it would go the other way around. Would have been far more awesome to read that proof.
__________________
"Wake up, Luigi! The only time plumbers sleep on the job is when we're working by the hour."
Rathji is offline   Reply With Quote
Reply

Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT -6. The time now is 07:48 AM.

Calgary Flames
2023-24




Powered by vBulletin® Version 3.8.4
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Copyright Calgarypuck 2021