Monday, November 06, 2006

Warning label for an NP-hardness proof

A note about the proofs: Transformation arguments can be intricate and
highly formal. Furthermore, since the polynomially-equivalent problem might
not bear any obvious intuitive relation to the voting problem, the proof might
establish computational difficulty without seeming to explain its source. In this
sense, the conclusion is more important than the argument.
From "How hard is it to control an election?", by Bartholdi, Tovey, and Trick.

Categories: