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
Subscribe to:
Post Comments (Atom)
This article contains material about NP-completeness. NP-completeness is a theory, not a fact, about the complexity of computational problems. This material should be approached with an open mind, studied carefully, and critically considered.
ReplyDeletePosted by Luca