A simple explanation to P and NP

[andrewducker]

lebeautemps asked for a simple explanation of the whole P=NP thing that's been circulating the internet recently. I figured I'd give it a go - I'd appreciate it if the more knowledgable on my friends list could correct anything particularly stupid I'd said...

A "P" problem is one that is easily solved through a series of steps, without trying every single combination - such as "sort a bunch of names into alphabetical order". You don't have to try every single possible list of names in order to sort a list of names, you can just use a series of comparisons to shuffle them up and down until they're sorted.

An non-P problem is one that has no known efficient set of steps for producing an answer, and thus requires you to try possibilities until you find one that's right. A common example of one that is thought to be hard is The Travelling Salesman problem - "given a bunch of cities and a bunch of roads connecting them, what is the shortest route that will take the salesman to each city exactly once?" There's no known solution to this problem other than "start trying solutions and keep going until you've found one." (although there are ways of excluding obviously wrong answers quickly).

NP is the superset of all problems that are easy to check, P is the smaller subset of all problems that are easy to solve, and proving that they are the same thing would mean that all problems that are easy to check are also easy to solve.

One of the reasons this is important is that pretty much all of the security methods we use online rely on things like "integer factorization" not being P - the fact that we can multiply two large numbers together to get an answer very quickly, but breaking that large number back into the two component parts requires every possibility to be checked (which takes years/decades for very large numbers).

The recent fuss is because of a paper that was published claiming that P!=NP - i.e. that there are definitely problems that are easy to check, but not easy to solve. This would mean, for example, that there is no simple way to convert the big number back into its two components, and thus that all of our security is safe (from that particular direction, anyway).

Comments

[simont]

Among others. NP-complete problems are the hardest and/or most general ones in NP (in the sense that any other problem in NP can be written as an instance of them, so if you can solve an NP-complete problem then in principle you can solve all of NP), so certainly if anything in NP is not in P then the NP-complete problems are not.

However, there's no reason that all problems in NP but not in P are NP-complete. There could perfectly well be less general NP problems that are still too hard to be in P.

[cartesiandaemon.livejournal.com]

there's no reason that all problems in NP but not in P are NP-complete

Indeed, I seem to recall integer factorisation is in that class? I don't actually really understand this stuff, unfortunately, but iirc I remember Aaronson's blog saying that a quantum computer would help with integer factorisation, but would not help with NP-complete problems in general. But I'm not sure I understand correctly.

If I do, a minor nitpick might be to correct the last paragraph of the post, which says that P!=NP would mean that there is no efficient integer factorisation, to say that there probably isn't, or that there is no better solution to the travelling salesman problem[1].

[1] We soon need to replace "travelling salesman" with an equivalent network-routing problem to stay current with what most people are familiar with :)