Scott Aaronson, a US computer scientist, explained to BBC News why this problem was so significant.
"People sometimes use the analogy of a jigsaw - it can be hard to complete the jigsaw, but if someone has done it, it's pretty easy to check," said Aaronson.
The real question is, whether creativity can be automated or not, and Deolalikar's proof says that it can't.
If right, this solution can have very important applications, right from cracking codes to airline scheduling.
However, Aaronson said that Deolalikar's proof might fail a 'sanity test.'
Which means, he should ensure that it only proves things we know are true, and not something that we know is false.
"Everyone agrees, said Aaronson, "if he can't answer this, the proof is toast."
One, who finds the solution of P&NP millennium Prize Problems, will receive prize money of a million dollars.