HP Labs scientist Vinay Deolalikar, answers ‘No’ to 100 million dollar question

13 Aug 2010

1

Vinay DeolalikarAn 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.

Business History Videos

History of hovercraft Part 3 | Industry study | Business History

History of hovercraft Part 3...

Today I shall talk a bit more about the military plans for ...

By Kiron Kasbekar | Presenter: Kiron Kasbekar

History of hovercraft Part 2 | Industry study | Business History

History of hovercraft Part 2...

In this episode of our history of hovercraft, we shall exam...

By Kiron Kasbekar | Presenter: Kiron Kasbekar

History of Hovercraft Part 1 | Industry study | Business History

History of Hovercraft Part 1...

If you’ve been a James Bond movie fan, you may recall seein...

By Kiron Kasbekar | Presenter: Kiron Kasbekar

History of Trams in India | Industry study | Business History

History of Trams in India | ...

The video I am presenting to you is based on a script writt...

By Aniket Gupta | Presenter: Sheetal Gaikwad

view more
View details about the software product Informachine News Trackers