[EM] A computationally feasible method (algorithmic redistricting)

[Kristofer Munsterhjelm]

Juho wrote:
> On Sep 4, 2008, at 0:59 , Kristofer Munsterhjelm wrote:
>> 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).
> 
> Puzzles and ciphers are good examples of cases where general 
> optimization may typically fail to find even a decent answer (well, in 
> these example cases the solution must be 100% good or it is no good at 
> all). My assumption was that in the area of voting methods it would be 
> typical that general optimization methods are sufficient and will with 
> good probability lead to good enough results. Are there and 
> counterexamples to this?

That gets harder, since most puzzles are of the "right or not" quality. 
Games could count, but it muddies the situation because if games are 
*-complete, they're usually PSPACE (because you have to come up with 
something that works for all possible replies).

However, games that have rules governing the dynamics could be used. For 
instance, finding out where to put the pieces in a Tetris game in the 
absolutely best manner possible is NP-complete. Still, people manage to 
play Tetris, because their approximations are good enough (or not, in 
which case they usually lose at higher levels) and because the 
situations aren't critical.

The problem with using these examples is that you lose the explaining 
power. If you tell someone that placing pieces optimally in Tetris is 
NP-complete, he won't get it, since to him Tetris is easy up to a 
certain point (assume this is someone who knows how to play it), and the 
reason he loses at a sufficiently level is because he can't approximate 
fast enough, which probably has very little to do with asymptotic 
complexity and rather much to do with the constants in the term.

So you'd have to use puzzles to explain the all-or-nothing version and 
only then go on to the optimization version.

Note that I fudged my own explanation a bit here: optimal anything isn't 
NP-complete, it's NP-hard. It's decision problem ("is there a way of 
doing it better than x by some given measure") that's NP-complete, and 
you can find the optimum (best value of x possible) by doing a binary 
search.