4 ms·

P versus NP isn't hard to explain if some of the problems are first familiar with the person you're explaining it to. "It's very easy to check if sudoku is cor

P versus NP isn't hard to explain if some of the problems are first familiar with the person you're explaining it to. "It's very easy to check if sudoku is correct, right? You just go line by line, box by box. But isn't it fairly hard to solve?" You'd have to go more in-depth than that, you're right: there's not a good one or two sentence explanation. But, explaining that "some things are really easy to check if they are correct, but really hard to solve: what does easy and hard mean? generally, it means it takes either a short time (easy) or a long time (hard)" isn't too bad.

dgacmu 9y ago
I can't do it in two sentences, but this is approximately the version I teach to first-year non-CS undergrads: A problem is called "NP" if I can give you a solution to it and you can easily verify that the solution is correct. For example, "find 3 different odd numbers that together add up to ten" (here's a possible solution: 3, 5, 7). What's awesome about this is that there are a lot of problems of that form where we don't know whether or not it's possible to find a solution to the problems before dying of old age -- or before the sun runs out of fuel, even though you could check the answer in a few minutes using pencil and paper. Nobody has ever figured out how to solve them fast, but it's a huge open question of whether they can be solved fast. The P = NP question is whether there exists a fast solution to any problem that you can verify easily if I give you a solution. And it's not just of theoretical interest: some those problems underlie everything from cryptography (communicating and storing information securely using encryption) to things like optimizing airline routes or the way UPS chooses where to route packages. Amazingly, there's a set of problems that if you find way to solve any one of them fast, you can solve all problems in NP fast. Which means the NSA and everyone else will try to kidnap you to find out the secret. Fortunately, most people who study it don't think that there's a solution. But it's one of the most famous and important problems in computing, and nobody -- of some of the smartest people in the field -- has ever managed to prove it either way. (Truth in advertising: We actually use subset sum as the example, and walk through it a little, but that's because we're trying to teach it in more detail than just telling the story. And have also taught a handwavy version of asymptotic analysis. If you want to show someone how hard it gets quickly, subset sum is a nice way to do it. The "talking" example above is, of course, an instance of subset sum, but it doesn't explain the general form of the problem.)
- odonnellryan 9y ago
  Isn't it a little misleading to say a problem is NP "if I can give you a solution to it and you can easily verify that the solution is correct." Not all problems that fit that description fall into NP, right?
  - dgacmu 9y ago
    I can only think of a few ways in which my definition fails. First, that it doesn't identify that NP only requires polytime verifiability for satisfying answers, not for "no" answers; second, that the use of the informal "you" instead of "a deterministic Turing machine" makes assumptions about the bounds of human reasoning that I assume are correct but don't know for certain; and third, that the ease of verifying certain solutions may mislead a lay-observer into thinking that a problem is in NP when, in fact, it is harder. ("This program exits because it consists only of the single statement exit(0);"). I think the third problem with my definition is the most thorny. But if you take the technically accurate form form of it that doesn't risk confusing easy instances with worst-case behavior - that you can verify in polytime a solution to any instance of the problem - it's technically correct. But which things did you have in mind, and how would you improve the explanation?
  - popcorncolonel 9y ago
    No, that's what NP means. Given a witness to a solution of a problem, verifying that the solution is correct in polynomial time means the problem is in NP.

dgacmu 9y ago

I can't do it in two sentences, but this is approximately the version I teach to first-year non-CS undergrads: A problem is called "NP" if I can give you a solution to it and you can easily verify that the solution is correct. For example, "find 3 different odd numbers that together add up to ten" (here's a possible solution: 3, 5, 7). What's awesome about this is that there are a lot of problems of that form where we don't know whether or not it's possible to find a solution to the problems before dying of old age -- or before the sun runs out of fuel, even though you could check the answer in a few minutes using pencil and paper. Nobody has ever figured out how to solve them fast, but it's a huge open question of whether they can be solved fast. The P = NP question is whether there exists a fast solution to any problem that you can verify easily if I give you a solution. And it's not just of theoretical interest: some those problems underlie everything from cryptography (communicating and storing information securely using encryption) to things like optimizing airline routes or the way UPS chooses where to route packages. Amazingly, there's a set of problems that if you find way to solve any one of them fast, you can solve all problems in NP fast. Which means the NSA and everyone else will try to kidnap you to find out the secret. Fortunately, most people who study it don't think that there's a solution. But it's one of the most famous and important problems in computing, and nobody -- of some of the smartest people in the field -- has ever managed to prove it either way. (Truth in advertising: We actually use subset sum as the example, and walk through it a little, but that's because we're trying to teach it in more detail than just telling the story. And have also taught a handwavy version of asymptotic analysis. If you want to show someone how hard it gets quickly, subset sum is a nice way to do it. The "talking" example above is, of course, an instance of subset sum, but it doesn't explain the general form of the problem.)

odonnellryan 9y ago
Isn't it a little misleading to say a problem is NP "if I can give you a solution to it and you can easily verify that the solution is correct." Not all problems that fit that description fall into NP, right?
- dgacmu 9y ago
  I can only think of a few ways in which my definition fails. First, that it doesn't identify that NP only requires polytime verifiability for satisfying answers, not for "no" answers; second, that the use of the informal "you" instead of "a deterministic Turing machine" makes assumptions about the bounds of human reasoning that I assume are correct but don't know for certain; and third, that the ease of verifying certain solutions may mislead a lay-observer into thinking that a problem is in NP when, in fact, it is harder. ("This program exits because it consists only of the single statement exit(0);"). I think the third problem with my definition is the most thorny. But if you take the technically accurate form form of it that doesn't risk confusing easy instances with worst-case behavior - that you can verify in polytime a solution to any instance of the problem - it's technically correct. But which things did you have in mind, and how would you improve the explanation?
- popcorncolonel 9y ago
  No, that's what NP means. Given a witness to a solution of a problem, verifying that the solution is correct in polynomial time means the problem is in NP.