## P = NP?

August 21, 2010

P is not equal to NP, isn’t that simple enough? So what’s all the fuss about; well ask mathematicians and computer scientists who have been working to find the answer but have been unsuccessful.

Many of you who have been following science news and blogs must have heard the buzz about solution to P vs NP problem recently. For past couple of weeks, I have been taking off from blogging and basically the net itself (not to much success), so I missed the news until my friend Vishwesha told me about it couple of days back and told me how it has been making buzz in the blogosphere. Not just the bloggers but famous mathematicians jumped into it and provided critical review and analyis to the solution and finally it was concluded that there are many flaws in the solution. Vishwesha wrote quite a bit about the public review of the proof in his blog.

Here I will just to try to write about what P vs NP problem is, why it is so critical and alo provide various links for further reading. P vs NP is one of the seven unsolved problems in Mathematics for which Clay Mathematics Institute offers million dollars for providing the solution. Till now only one of the problems, Poincaré conjecture, has been resolved for which Russian mathematician Dr. Grigoriy Perelman was awarded the million dollar prize, but interestingly he refused to accept the reward and went into recluse in Russia. P vs NP problem was first formulated by Stephen Cook in 1971 and official formulation can be found here. In layman terms, P Vs NP problem asks the question whether a “hard” problem, whose solution can be easily verified, can it also be solved easily by a computer algorithm? Got confused? Ok, let’s try to understand more clearly.

P= NP?

P stands for polynomial time and here it refers to set of problems whose solution can be determined by computer algorithm in polynomial time proportional to number of elements N. These problems are said to be solved easily. For a problem with N elements in it, algorithm execution time is polynomial : N, N2, N3 and so on. Higher the order of power slower is the execution.

NP here stands for ” Non-deterministic Polynomial” and consists of set of those problems for which solutions are very hard to obtain, but once solutions are given, its easily verifiable in polynomial time. In terms of algorithm execution time, the solution finding times for NP problems are exponential where a number is raised to the Nth power, like, say, 2N. Time taken to solve is huge and practically impossible to solve.For example, it’s very hard to find prime factors of a very large number but once the solution is available, it can be verified simply by multiplying the factors which can be done in polynomial time. Many of the real life problems come under NP category, such as scheduling optimization problem (stochastic algorithms are used to solve such problems in real-life). Clay Institute provides another example to understand the NP type problem:

Suppose that you are organizing housing accommodations for a group of four hundred university students. Space is limited and only one hundred of the students will receive places in the dormitory. To complicate matters, the Dean has provided you with a list of pairs of incompatible students, and requested that no pair from this list appear in your final choice. This is an example of what computer scientists call an NP-problem, since it is easy to check if a given choice of one hundred students proposed by a coworker is satisfactory (i.e., no pair taken from your coworker’s list also appears on the list from the Dean’s office), however the task of generating such a list from scratch seems to be so hard as to be completely impractical. Indeed, the total number of ways of choosing one hundred students from the four hundred applicants is greater than the number of atoms in the known universe! Thus no future civilization could ever hope to build a supercomputer capable of solving the problem by brute force; that is, by checking every possible combination of 100 students. [Clay Institute]

So P= NP? question means that for a hard problem whose solution can be verified in Polynomial time, can it also be solved in Polynomial time. In other words, is the apparent ‘hard’ problem really hard or not? Till now, no one has been to prove or disprove this problem, while majority of mathematicians believe that P is not equal to NP, implying that for a hard problem whose solutions can be verified easily, finding solution is impossible even by the best algorithm.

Recently Vinay Deolalikar from HP claimed that he has solved the problem and claimed P is not equal to NP. His manuscript can be found here. He sent out his results and proof to mathematicians and what followed was a collaborative public reviewing of the proof from famous mathematicians to students to bloggers. Mathematicians found many gaping holes in the proof.

Some might ask, how does it help knowing that we cannot solve a very hard problem. Well, Dr Sipser from MIT rightly explains the importance of knowing the proof of whether P=NP or not:

He says that the P-versus-NP problem is important for deepening our understanding of computational complexity. “The P-versus-NP problem has become broadly recognized in the mathematical community as a mathematical question that is fundamental and important and beautiful.” [MIT]

You can also follow this link to get a detailed list of related articles and links and ofcourse Wikipedia. You an also follow Georgia Tech proffesor, R J Lipton’s blog which provides indepth analysis and discussion. He also gives three reasons as to why we need proof for this problem:

Does A Proof Of P${\neq}$NP Matter?

Yes it does. Here are my three foremost reasons to think that such a proof could be very important.

${\bullet}$ A Proof Would Tell Why: Even those who are sure that P${\neq}$NP would like to know why this is so. This is exactly Atiyah’s point. A proof would give us insight into why there can be no efficient search for SAT.

${\bullet}$ A Proof Could Give Us New Methods: Perhaps the best reason is the hope that a proof that P${\neq}$NP would have to use new tools in the proof. These tools would hopefully shed light on computation in general. They could yield insights into the fundamental nature of computation. This is the best reason, in my opinion, for wanting a proof.

${\bullet}$ A Proof Helps With Goals of Security: Modern cryptography uses the term provable security. In many cases this means only that they have proved that breaking their system implies that some hardness assumption, such as on factoring, is wrong. Even a proof that P${\neq}$NP would not rule out that such assumptions are false: recall that factoring is not known to be NP-complete. I think, however, that a proof of at least P${\neq}$NP would be of some comfort to cryptographers. Their special hardness assumptions might still be unproved, but a proof would move us closer to perhaps one day really having provable security. [R J Lipton blog]

Filed under: Science

Tags: ,

(required)

(required), (Hidden)

XHTML: You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

## Born on this day

August 4, 2020
1792 Percy Busshe Shelley
1870 Sir Harry Lauder
1900 H.M. Queen Elizabeth Queen Mother
1901 Louis Armstrong
1908 Sir Osbert Lancaster
1913 Victor Mature
1941 Martin Jarvis
1943 Georgina Hale
1952 Marie Brennan
Joe's