A note about the proofs: Transformation arguments can be intricate andFrom "How hard is it to control an election?", by Bartholdi, Tovey, and Trick.
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.
Monday, November 06, 2006
Warning label for an NP-hardness proof
Posted by Suresh Venkatasubramanian at 11/06/2006 11:28:00 PM