[EM] A computationally feasible method (algorithmic redistricting)

[Juho]

The traditional algorithm complexity research covers usually only  
finding perfect/optimal result. I'm particularly interested in how  
the value of the result increases as a function of time. It is  
possible that even if it would take 100 years to guarantee that one  
has found the best solution, it is possible that five minutes would  
be enough to find a 99% good solution with 99% probability.

Decrypting ciphered text does not work this way (the results could  
still be worth 0 after 10 years with good probability). But solving  
e.g. CPO-STV may well behave more this way (probably one can find an  
80% good solution in one minute). Good performance in value/time  
means that general optimization works (and the method can be  
considered feasible in practice despite of being theoretically  
infeasible).

Juho


On Sep 5, 2008, at 1:28 , Kristofer Munsterhjelm wrote:

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


		
___________________________________________________________ 
Now you can scan emails quickly with a reading pane. Get the new Yahoo! Mail. http://uk.docs.yahoo.com/nowyoucan.html