Posted by: dhaleyjr | September 25, 2008

Overview of P vs NP

Being a CS concentrator, I’m naturally drawn to the mathematical questions dealt with in computer science. By far the most well-known, unsolved question in the field is whether P=NP. If this equality were true, the implications would be remarkable. As an example, cryptography would no longer work meaning “secure” transmissions would no longer be secure at all… so much for using credit cards online, encrypting emails, etc. Even more incredible is that mathematicians would not be needed for finding proofs; a computer could systematically find a proof for any theorem for which a reasonably sized proof exists.

Okay, so P=NP is important, and not just in the realm of abstract math. But “P=NP” is a pretty weird and meaningless statement for anyone not knowledgeable of the terms. I’d like to use this post to explain the basics of the problem.

The Class P

Essentially P and NP are two classes of problems. The class P refers to problems which can be solved quickly, or more specifically, in polynomial time compared to the input. What this means is that if you give an input of length n, you can determine the answer in polynomial time in relation to n.

For example, determining if a number in base 10 is divisible by 3 is a polynomial problem. You’re given a number with n digits. To determine the answer you can add the digits mod 3 together. If the total is 0, the number is divisible by 3, otherwise it’s not. Since each digit must be mod’ed by 3 and added to the next, there are essentially 2 steps per digit. There are n digits. So in total it took 2n steps. This is simplified greatly but explains the basic idea. 2n is polynomial with respect to n. So our algorithm for determining divisibility by 3 is in polynomial time.

As long as our algorithm contains only a polynomial number of steps with respect to the input, the problem is considered in class P. It could take 100n, n^2, or even 100*n^100 steps but it would still be polynomial.

The Class NP

The class NP are problems which can be solved in exponential time, or 2^n for example (or 10^n or 1000^n, etc). [Edit: As noted by an alum reader, this is a misstatement. NP is the class that can be verified in polynomial time. No one has yet proved that NP = exponential time. However, it can be helpful to think of exponential problems when considering NP.] Whereas P was loosely defined as problems which can be solved quickly, NP is described as problems which can be verified quickly (in polynomial time).

Factoring a number is considered an NP problem. There is no known method for doing it in polynomial time. But given a solution, it is very easy to check if it’s correct. For example, if I said factor 62,615,533, it would probably take you a while. But if i said its factorization is 7907 x 7919, you could verify this quickly by simply multiplying them together. Solving the problem takes a long time while verifying a solution is quick. These problems are of the class NP.

What This Means

So coming back to the question of P=NP. Clearly if a problem is in P it is also in NP since polynomial time < exponential time (for large enough input size). However it is not clear if P is merely a subset of NP or if P actually equals NP. No one has been able to prove whether or not P=NP. This means that although no one has found a polynomial time proof for any NP-complete problems (for definition, see: http://en.wikipedia.org/wiki/Np-complete), no one has proved that one doesn’t exist. If a polynomial-time algorithm for any NP-complete problem is found then it would mean that all NP problems have a polynomial time solution.

P=NP is a problem that anyone interested in math or CS should be aware of since it is one of the most important unsolved questions. If P were to equal NP, then factoring large numbers could be done efficiently meaning that cryptography (which relies on factoring being a difficult problem) would be impossible with the current methods. In fact most problems which are considered computationally hard could suddenly be solved efficiently. Essentially it would mean that if you could verify an answer quickly, you could also determine that answer quickly, which is a pretty wild concept.

Finally, an xkcd comic I found amusing since many people I know, myself included, fit this description: http://xkcd.com/356/

Advertisements

Responses

  1. The question of P=NP is a very intriguing one and I enjoyed your post about it!

    You point out that it has consequences for cryptography, and I thought I would comment on that since I do a bit of cryptography myself. Things get very muddy when you get into practical cryptography. For example, consider an algorithm that is not polynomial: suppose we consider one that takes 2^N time. Now consider a polynomial algorithm taking 2^{1024}N time. The exponential always takes longer if N is big enough, say N > 1034. For smaller N, however, the exponential algorithm is better! Real cryptographic implementations live in a certain window of sizes of N, depending on the architecture of the machine or device that’s running the algorithm and other limitations. So whether an algorithm is polynomial may not matter right now (although it means it will eventually matter, as machines get faster and computation cheaper, etc.)

    This means I sometimes find practical cryptographers are amazingly not too interested in P=NP, because for them it doesn’t matter if factorisation is polynomial: only whether you can do it with your laptop this year. In particular, if someone proves that P=NP today, it may not actually provide a feasible algorithm for factoring on today’s computers, and the internet will probably not just stop working overnight. Still, it would be very exciting and crazy times.

    Some people view math in a very practical way, as a tool to get very specific results. Sometimes this prompts the “pure” to scoff at the “applied.” But as Kristin Lauter of Microsoft Research once pointed out to me, pure mathematics can and should draw inspiration from applied mathematics. Things like P=NP are wonderful examples of the sorts of fascinating mathematical questions that come out of application (computer science or cryptography), but are also very attractive and beautiful questions in their own, pure, form.

    This observation is a little bit of a segue into ardaayvaz’s next post, which discusses the differences between mathematics for mathematics’ sake and the application to the real world.

  2. dog….

  3. Hi! I was surfing and found your blog post… nice! I love your blog. 🙂 Cheers! Sandra. R.

  4. Sign: umsun Hello!!! rcuwwymhyw and 1843ssgfhphzye and 9824Sorry, what did you mean?? A??

  5. Sign: zdbrw Hello!!! rtwav and 3116xuvekbqwrd and 7141 : Nice blog!


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: