« Back to #tips
Avatar for atlasfugged atlasfugged
10 Aug 2010 9:52 PM
One of the most important and confounding questions in all of computer science is whether all decision problems (i.e. problems whose solutions are either YES or NO) with solutions that can be quickly verified by a computer are simultaneously decision problems whose solutions can be quickly computed. In other words, if the solution of a decision problem can be checked quickly, then does it follow, necessarily, that the solution can also be determined quickly? This question is referred to as the "P versus NP problem" or "P = NP?". It was one of the so-called Millennium Problems. (Recall that, earlier this year, Russian wierdo, Grigory Perelman turned down the $1-million prize for resolving the Poincaré Conjecture, the first of the Millennium Problems to be considered solved). The "P" is how researchers in complexity theory (a branch of computer science) refer to the class of decision problems that can be solved quickly, P (polynomial-time) problems. The "NP" refers to the class of decision problems whose solutions can be verified quickly, NP (non-deterministic polynomial time) problems.

Vinay Deolalikar, a Principal Research Scientist at HP Labs, released a paper (PDF) on August 6 that may have solved the P versus NP problem. He demonstrated that there was at least one class of decision problems - he considered the Boolean satisfiability problem (SAT) in his proof - that was NP, but not P, thus contradicting the claim that P = NP. Deolalikar's work has yet to be thoroughly peer-reviewed and published, but so far it seems well received ( [rjlipton.wordpress.com] ).

via [www.newscientist.com]

#VinayDeolalikar #hp #hewlettpackard #np #p #computerscience #decisionproblems #mathematics #complexitytheory #computationalcomplexity #polynomialtime #turingmachines #pversusnp #millenniumproblems #clayinstitute

#tips
The Gadget Guide
More Stories…