Item — HN Reader

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."

1 comments

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.