HP Labs scientist Vinay Deolalikar, answers ‘No’ to 100 million dollar question
13 Aug 2010
An HP Labs scientist in California, Vinay Deolalikar has proposed a solution to the problem referred to in mathematics circles as 'Is P=NP?', in a paper published online running into a 100 pages.
The problem, among seven listed by the Clay Mathematic Institute carrying the Millennium Prize worth $1 million, refers to the possible equivalence of two classes of problems.
'NP' problems are those that may take different amounts of time to solve based on the data size, but each solution suggested can be easily checked.
An example of such types of problems is the jigsaw puzzle, which though it can be easily checked for the correctness of the solution, may be extremely difficult to solve.
On the other hand 'P' problems are those that scale in polynomial (a mathematical function that is the sum of a number of terms) time with the size of the data. An example of the type is the problem of alphabetically sorting of a list of names.
A computer can be programmed to sort the names very fast with addition of many more names adding to the difficulty of the task only to an extent and it would still be possible for the computer to handle it.