On Sep 4, 2008, at 0:59 , Kristofer Munsterhjelm wrote:
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).
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?
Juho
___________________________________________________________
The all-new Yahoo! Mail goes wherever you go - free your email address from your Internet provider. http://uk.docs.yahoo.com/nowyoucan.html
----
Election-Methods mailing list - see http://electorama.com/em for list info
