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.
----
Election-Methods mailing list - see http://electorama.com/em for list info
