Hacker News Reader

Comment by algolicious | Hacker News Reader

Actually, as an Ars commenter explains, Ars did kind of a bad job explaining NP. NP is the class of problems with an easily verified proof for existence, not the class of all exponentially solvable problems as they seem to imply (EXPTIME). Example: Is a boolean formula satisfiable? Provided an assignment for its variables, it is easy to check if it is a satisfying assignment.

View on HN

Explaining NP-complete to even a technically-educated audience is always tricky. Sometimes a somewhat misleading explanation is still going to get them closer to the important bits than a precise technical definition would.

I'd probably write: NP-complete refers to a special class of notoriously difficult problems. A solution to even one of them would lead to a solution to all of them, a development which could have radical real-world implications. (Insert good example here.)

I've had a lot of success explaining "easy to check a solution, but hard to come up with one" to people. It really doesn't matter whether people understand NP-complete and how polynomial reductions work. Just understanding what's included under NP is enough.

If I were writing this article, I'd explain NP as above, and then say "research now shows that there are many problems in NP on which quantum computers will offer no improvement."

I remember reading an example of "easy to check but hard to come up with" which is probably good for non-technical audiences. Its something like: You walk into a party and you want to know if you know anyone. To find out, you need to look at everyone and check. Alternatively, someone can point to someone and say "do you know John" and you can check that much faster.

However, I think that reductions are critical to understanding why we care about NP-complete problems so much. The best example I've been able to give of a reduction is "reducing" addition to subtraction.

Reply on news.ycombinator.com