Tab Completion

I'm Tab Atkins Jr, and I wear many hats. I work for Google on the Chrome browser as a Web Standards Hacker. I'm also a member of the CSS Working Group, and am either a member or contributor to several other working groups in the W3C. You can contact me here.
Listing of All Posts

A Quick Primer on P and NP

Last updated:

(This is a quick gloss over the problem, intended to give someone a good idea of what's going on without bogging down too much in details. Pretty sure I've gotten it right, but if I'm slightly off about something, don't worry about it.)

So, a lot of problems sit in P or NP complexity classes. This classifies a problem based on how quickly the time-to-solve increases as the size of the problem increases. Adding two numbers is linear - double the size of the numbers, you double the running time. Multiplying two numbers is (roughly) square - double the size of the numbers, you quadruple the running time. Bruteforcing a password is exponential - double the size of the password, you increase the running time by ~60^n (where n is the original size).

Linear and square are both "polynomial", or in P, because the relationship between problem size and running time can be written as a polynomial equation where the problem size is the base and the power is a static number. Adding is "size^1 = time", multiplying is "size^2 = time". Password cracking is not polynomial, because its equation is "60^size = time" - the size is a power, not a base.

NP doesn't quite stand for "non-polynomial", but it's often described as such, and that's pretty close to what it means. There's an extra wrinkle, though. NP actually stands for "non-deterministic polynomial", which means that if you had a magic 8-ball that you could ask yes/no questions of and it always gave the right answer, you could solve the problem in polynomial time. Bruteforcing passwords is like that - if you can just ask the oracle "is the first letter A? is it B?" etc, you can figure it out in linear time (roughly 60*N, rather than 60^N). A lot of exponential problems are like this - there's not actually that much work that goes into solving it, it's just that you don't know where to do the work, so you have to try every possible combination. The oracle fixes that.

An alternate definition of NP is that it requires at least polynomial time to solve, but only needs polynomial time to verify the solution. Again, passwords are like this - if someone claims they know the password, you can tell if they're right by just checking it against the real password, which is linear time (checking each letter).

The definition of NP technically covers everything in P as well. There's another category, NP-complete, which means "the hard part of NP". Most of the time, when people say "NP" they actually mean "NP-complete".

Quick diversion - it's still an open question whether P and NP are equal to each other. It might be that, with very clever algorithms, password cracking can be done in polynomial time. Most computer scientists don't think so, but we haven't yet been able to prove that it can't be done. (We can prove that some complexity classes are definitely different, but P and NP haven't been achieved yet.)

So, we don't yet know whether the NP-complete category is part of P (if P=NP) or is a hard chunk separate from P (if P!=NP). We do know, though, that some problems are definitely in NP-complete - they're the "hardest possible" problems in NP. (though, again, they might still turn out to be in P as well). We started out with 21 examples of NP-complete problems, and now we mostly add new ones by proving that you can transform the new problem into an NP-complete one and vice-versa (in polynomial time).

The NP-complete category is useful because it's big and connected, so that if anyone can ever prove that any single NP-complete problem is in P, they prove that they're all in P automatically.

(a limited set of Markdown is supported)