P or NP, that is the question!

How much to add a slash through the equals sign?

You may recall when we discussed the The Poincare Conjecture and that it was also one of the seven Clay Institute Millennium Prize Problems.  Those are seven of the most interesting and difficult open problems in math research as of May 24th, 2000.  One of the other Millennium Prize Problems is, in a line:

Does P = NP?

In the last few days the internet is abuzz with a discussion of a preprint by Vinay Deolalikar, a principal research scientist at HP which contains a claimed proof of P≠NP.  Heck, it’s already appeared on slashdot!  Where it was immediately analyzed by their experts (tongue in check, of course):

by Anonymous Coward writes: on Sunday August 08, @06:31PM (#33183704)

I mean, NP has an N in front of the P. That’s obviously not the same as P. Also, P != HP.

and:

by Anonymous Coward writes: on Sunday August 08, @06:39PM (#33183766)

“I mean, NP has an N in front of the P. That’s obviously not the same as P. Also, P != HP.”

If you knew really advanced mathematics you’d know that NP means N times P. So NP does equal P when N=1. But not the rest of the time. Oh and it does when P=0. How much was that prize again?

We at OU MathClub HQ aren’t qualified to evaluate the correctness of the paper.  But we can say a few things.

One the one hand, people were amazed in 2002 when Manindra Agrawal, Neeraj Kayal and Nitin Saxena announced a polynomial time test for the primeness of an n digit number (Kayal and Saxena were undergraduates!) in a paper called “PRIMES is in P”.  And, of course, there is the now famous case of Pereleman and the Poincare Conjecture.

On the other hand, slashdot themselves posted about another proof of P not equal to NP and in 2008 and announced a proof of the famous Riemann Hypothesis (both of which turned out to have fatal errors).

If you’d like to read along as experts analyze the proof, then check out the blog posts of Scott Aaronson or Richard Lipton.

We’ll satisfy ourselves by briefly talking about the question itself.  P and NP are shorthand within complexity theory (a branch of theoretic computer science/mathematics).

P stands for problems which can be solved by an algorithm which runs in polynomial time; that is, there is an algorithm which can solve the problem and the amount of time it takes is a polynomial function of the size of the input.  For example, finding the GCD of two integers is a problem in P.  Another example, thanks to the AKS algorithm mentioned above, is testing whether a given number is prime or not.

NP are problems for which there does not necessarily exist an algorithm to find an answer in polynomial time, but there does exist a way to test the answer within polynomial time.  If a problem is in P, then it is in NP since we don’t forbid polynomial time solutions.  So we always have

P \subseteq NP

For example, imagine I have a combination lock with 10 numbers on the dial and the combination is n numbers long.  If you find the combination by an exhaustive (and exhausting!) search, then you will have to check 10^n different combinations.  That is, solving the problem by direct search is exponential as a function of how many numbers are in the combination.  But if I give you the solution, you can check it in a small amount of time (polynomial in the number n).  That is, this dumb algorithm shows that the problem is at least in NP.

But of course if I was much more clever, then I could perhaps come up with a solution which actually is polynomial in n.  The million dollar question is then, does there actually exist problems which are in NP but not in P?  That is, are there problems which cannot be solved in polynomial time?

Of course this is an interesting problem for us math folks, but why should your mom care?  Well, if she shops online, then very likely the encryption used depends on it being very, very hard to factor large numbers.  What does very, very hard mean?  To be precise, there is no known algorithm to factor large numbers which is of polynomial time.  Factoring is an example of a NP problem.   It took over 2 years to factor a 232 digit number using a large number of computers.  Which means that the by the time people have factored the number and cracked the code, your mom (and her credit card number) is long gone from the amazon website.

Of course, if P= NP, then that means that there is a polynomial time algorithm to factor large numbers.  If someone finds that algorithm, then internet security, banking, and the folks at the NSA are suddenly going to have their hands full!  Society is banking on the fact that factoring integers is in NP but not P.

It would be reassuring to know that indeed, P \neq NP!  Homer Simpson, though, doesn’t seem worried about it:

Advertisements

2 thoughts on “P or NP, that is the question!

  1. I attended a talk this saturday by Prof. Narendra S. Chaudhari on a possible proof for P=NP. A polynomial time algorithm O(N^13) for solving the 3SAT problem. from various angles this seemed to be the answer for the famed problem. In this non-DFS approach the key issue seems to be the representation step that inherently avoids the exponential time complexity. Please check out the paper published in Indian Journal of Mathematics and Slides of the talk by this unassuming man at http://dcis.uohyd.ernet.in/~wankarcs//index_files/seminar.htm.

    Very very exciting times when there are two serious attempts one by Deolalikar at P != NP and a constructive proof of Chaudhari for P=NP.

  2. I was unaware of the attempted solution of Vinay Deolalikar. I hope someone gets there soon enough. Everybody wants that one million, even I. The only problem is – I am not that good at math. Anyways, good informative post.

Comments are closed.