Is P vs NP solved?

August 8, 2010 · Posted in innovation, problem solving 

Vinay Deolalikar from HP Labs claims he may have solved the P vs NP problem proving that P ≠ NP. It’s literally a million dollar problem. Millennium Prize is offering $1,000,000 for the solution. This is very important for a range of problems including: cryptography, logistics, biology, mathematics, and innovation.

If P ≠ NP is true, it would allow a person to formally show that a problem cannot be solved efficiently, so attention could be focused on partial solutions or solutions to other problems. Or as I say in my talks about applying information theory to science, “Being able to prove something is impossible helps you focus on the things that might be possible.”

The other implication is that some problems can be proven to be harder to solve than to test that the solution is true. This is very important to cryptography. If P = NP then many of the encryption methods would be easy to break and would need to be changed.

Hard to solve, easy to check also directly relates to innovation. I run into this all the time. A company has what they believe is an impossible problem. After we apply the Predictive Innovation® and find the solution they think the solution was obvious. It was far easier to check the answer than it was to solve the problem. In fact it was so easy to check the answer they didn’t understand why it was so hard to find in the first place. I would not be surprised if P ≠ NP was proved.

Tags: , , , , , , , , ,

Comments