[EM] A computationally feasible method (algorithmic redistricting)

[Kristofer Munsterhjelm]

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