Explain the proof by Vinay Deolalikar that P != NP

math computer-science complexity-theory proof p-np
Nixuz picture Nixuz · Aug 9, 2010 · Viewed 17.9k times · Source

Recently there has been a paper floating around by Vinay Deolalikar at HP Labs which claims to have proved that P != NP.

Could someone explain how this proof works for us less mathematically inclined people?

Answer

Michael Anderson picture Michael Anderson · Aug 9, 2010

I've only scanned through the paper, but here's a rough summary of how it all hangs together.

From page 86 of the paper.

... polynomial time algorithms succeed by successively “breaking up” the problem into smaller subproblems that are joined to each other through conditional independence. Consequently, polynomial time algorithms cannot solve problems in regimes where blocks whose order is the same as the underlying problem instance require simultaneous resolution.

Other parts of the paper show that certain NP problems can not be broken up in this manner. Thus NP/= P

Much of the paper is spent defining conditional independence and proving these two points.

Related questions

Missing number(s) Interview Question Redux

The common interview problem of determining the missing value in a range from 1 to N has been done a thousand times over. Variations include 2 missing values up to K missing values. Example problem: Range [1,10] (1 2 4 5 7 8 9 10) = {3,6} Here is an example of the …

Read More
What is "entropy and information gain"?

I am reading this book (NLTK) and it is confusing. Entropy is defined as: Entropy is the sum of the probability of each label times the log probability of that same label How can I apply entropy and maximum entropy …

Read More
Math for computer science

I have read several answers on this topic , but I still have questions.. There are plenty of math courses, and I don't know which one to take first. Which math classes should every computer scientist take? And what class should …

Read More