#1) On August 11, 2010 at 2:14 PM,
portefeuille (98.49) wrote:

-------------

P vs NP Problem Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

#5) On August 11, 2010 at 4:50 PM,
WallstreetKnight (38.12) wrote:

Do you think the proof will 'stand?'

From a non-computer science point of view, wouldn't P=/=NP be sort of a downer? It confirms what a lot of people suspect but does it contribute to many applicable breakthroughs?

## 9 Comments – Post Your Own

#1)On August 11, 2010 at 2:14 PM,portefeuille (98.49)wrote:-------------

P vs NP Problem Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker's list also appears on the list from the Dean's office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. However, this apparent difficulty may only reflect the lack of ingenuity of your programmer. In fact, one of the outstanding problems in computer science is determining whether questions exist whose answer can be quickly checked, but which require an impossibly long time to solve by any direct procedure. Problems like the one listed above certainly seem to be of this kind, but so far no one has managed to prove that any of them really are so hard as they appear, i.e., that there really is no feasible way to generate an answer with the help of a computer. Stephen Cook and Leonid Levin formulated the P (i.e., easy to find) versus NP (i.e., easy to check) problem independently in 1971.

-------------

(from here)

Report this comment#2)On August 11, 2010 at 2:22 PM,portefeuille (98.49)wrote:http://en.wikipedia.org/wiki/P_versus_NP_problem

Report this comment#3)On August 11, 2010 at 2:43 PM,portefeuille (98.49)wrote:also see this post.

How eating chocolate can help improve your maths

#4)On August 11, 2010 at 2:57 PM,portefeuille (98.49)wrote:updated version of the paper.

http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_8_11.pdf

Report this comment#5)On August 11, 2010 at 4:50 PM,WallstreetKnight (38.12)wrote:Do you think the proof will 'stand?'

From a non-computer science point of view, wouldn't P=/=NP be sort of a downer? It confirms what a lot of people suspect but does it contribute to many applicable breakthroughs?

Report this comment#6)On August 11, 2010 at 5:58 PM,portefeuille (98.49)wrote:#5 see here.

http://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_proof

Report this comment#7)On August 15, 2010 at 10:29 PM,portefeuille (98.49)wrote:Tide turns against million-dollar maths proof

Fatal Flaws in Deolalikar’s Proof?

The P≠NP “Proof” Is One Week Old

#8)On August 18, 2010 at 1:19 AM,portefeuille (98.49)wrote:Now, It’s The Slow Roasting Of An HP Mathematician

Report this comment#9)On August 18, 2010 at 9:48 AM,TigerPack1 (36.85)wrote:I hope you can join us tomorrow night at the LIVE Chat on TMFJake's blog... to discuss our WSS practice portfolios.

http://caps.fool.com/Blogs/live-chat-this-thursday/435184

Our "besthedgefundideas" seems to follow ATPG up and down each day lately!

I am still trying to figure out my Rubik's Cube in 21 moves or less!

-TigerPack

Report this comment