Brian Olson wrote:
I guess my time in Computer Science land has left me pretty comfortable
with the idea that there are lots of problems that are too hard to ever
reliably get "the best solution". I don't know if there's a short-short
popularizing explanation of how finding a good solution is Hard while
measuring the quality of a solution is pretty quick.
If anybody asks and it's not the time, place, or audience for discussing
NP Hard problems, I will wave my hands and say, "Hey, look over there!
Good results, on my one puny computer! With more it'd only get better!"
I think puzzles and games make good examples of NP-hard problems.
Sokoban is PSPACE-complete, and it's not that difficult to show people
that there are puzzles (like ciphers) where you know if a solution is
right, but it takes effort to find the solution. That's pretty much the
point of a puzzle, after all (although not all puzzles are NP-hard; they
can be fun even if they're not, as long as they do something for which
it's challenging to find a solution).
----
Election-Methods mailing list - see http://electorama.com/em for list info
