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