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

[call-waiting.livejournal.com]

I should point out is that the proof (if it's valid) is that P != NP, which is far less interesting than P = NP...

[call-waiting.livejournal.com]

Oh, and the travelling salesman problem is not just to find a valid route, but the shortest route.

[andrewducker]

Fixed!

[andrewducker]

Fixed that moments before you replied :->

[ciphergoth.livejournal.com]

An "NP" problem is one that has no known set of steps for producing an answer

No, an NP problem is any problem where you can efficiently check the answer. All problems in P are in NP, for example. What's known about a problem doesn't affect what complexity class it's in.

[andrewducker]

Aaah. Am I thinking of NP-Complete problems?

[ciphergoth.livejournal.com]

I don't think so.

Before I get to that - it's also not true to say that problems in NP which are not known to be in P are those where you have to try every combination to find a solution. There might be much more efficient search strategies than that, which cut out huge chunks of the search space, but don't manage to actually be polynomial time. In particular, they don't have to be exponential time - lots of algorithms are super-polynomial but sub-exponential.

NP-complete means roughly "as hard as any problem in NP". A polynomial-time algorithm for any NP-complete problem could be used to solve *any* problem in NP in polynomial time, using a device called a "reduction".

[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 :)

[simont]

An "NP" problem is one that has no known set of steps for producing an answer, and thus requires you to check every possibility until you find one that's right.

Doing that is a set of steps for producing an answer! You probably meant to say "no efficient set of steps" here, or some such.

Also, technically, NP is a superset of P – there's no implication that "an NP problem" doesn't have a polynomial-time solution. Colloquial usage is to only describe problems as NP if they aren't (known to be) in P, on the pragmatic basis that if they were easier than that you'd have said so, but that's not what it really means.

I think the major thing I would add to this explanation is a paragraph explaining why the question is open, along the lines of:

At first sight it seems obvious that NP is a bigger class of problems than P, or in other words, that when a problem looks as if it needs you to go through all the possibilities one by one it's likely that there is in fact no quicker way to solve it. However, it turns out that this is surprisingly hard to prove (or disprove), so there's still a possibility in principle that the classes P and NP might turn out to be identical – which would mean that any problem for which you could efficiently check a candidate solution would also have an efficient way of finding a solution from scratch. Most computer scientists believe this is not true, and that P and NP are just as different as they appear, but a proof would be big news either way. (Though it would be bigger news if it went the surprising way and said that P and NP were equal.)

[andrewducker]

Cheers - I've updated it, does it make more sense now?

[simont]

It still says that a non-P problem is one for which there's no known efficient algorithm. The whole point of P possibly being equal to NP is that all those problems might turn out not to be non-P after all :-)

Perhaps move the bit about our limited knowledge down to the TSP sentence? So that a non-P problem is simply described as "one which has no efficient set of steps", and then "A common example of a problem which is thought to be hard in this way is The Travelling Salesman problem...".

[andrewducker]

Cheers - I'll make those changes when I get back from a one-to-one with my manager :->

[ciphergoth.livejournal.com]

Also lots and lots of public-key cryptography doesn't depend on integer factorization being hard - other important hard problems include the discrete logarithm problem in Z*_p, or in a group based on elliptic curves, or the computational Diffie-Hellman problem or the Decisional Diffie-Hellman problem or... lots of other things.

And in cryptography, it's not worst-case hardness that matters - it's average case hardness.

If P turns out to equal NP, cryptography will have big problems - we'll be on the search for problems where the polynomial describing their hardness has a big exponent - but if we prove P != NP we'll still be a long way from having a cryptosystem we can prove good things about without making any assumptions about hardness.

[andrewducker]

Absolutely - that's why I said "from that direction" in that paragraph. I've added "like" to the bit about factorising numbers, to indicate that there are other methods, and rewritten the paragraphs above that, to take into account the stuff I got completely wrong about NP. Does it make a bit more sense now?

(And thanks - I really appreciate this)

[ciphergoth.livejournal.com]

I would drop all talk of trying lots of solutions; it's not just wrong in the details, it gives the wrong impression. For example, trying lots of solutions has nothing at all to do with how we actually attack integer factorization. Also you assume that all problems are NP - some problems, you can't even check the solution.

A P problem is one that can be solved in poly time.

An NP problem is one where you can check the solution in poly time.

If P != NP, there are problems that don't have efficient solutions, even though if we saw the solution we could efficiently check it.

[andrewducker]

I don't assume that all problems are NP - I say "NP is the superset of all problems that are easy to check".

I'm not going to mention poly time - the whole point was not to turn off people who go blank at the mention of things like that. I need to use examples that are in simple english, so that people can grasp at them. Without examples most people don't grasp things.

[andrewhickey.livejournal.com]

That's about as good an explanation as I've seen without getting into the technical details. You might, however, want to use a paraphrase of this explanation as to why it's important ( from http://www.scottaaronson.com/democritus/lec6.html - the best *technical* explanation I've seen, from a wonderful series of lectures on quantum computing):

"Dude. One way to measure P vs. NP's importance is this. If NP problems were feasible, then mathematical creativity could be automated. The ability to check a proof would entail the ability to find one. Every Apple II, every Commodore, would have the reasoning power of Archimedes or Gauss. So by just programming your computer and letting it run, presumably you could immediately solve not only P vs. NP, but also the other six Clay problems. (Or five, now that Poincaré is down.) "