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.


1 comment:

  1. 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.

    Posted by Luca


Disqus for The Geomblog