Warren is quite correct about: Re NP-hardness & polytime, all such results take place in an asymptotic limit as some parameter or parameters describing nput size tend to infinity. Say the input size is N bits; then an algorithm is polytime if its runtime is <P(N) steps where P is a polynomial.
For the question of spotting IRV nonmonotonicty, the question of determining your strtaegic-best IRV vote, etc, if V (#voters) is large and C (#canddts) is fixed then the runtime is polynomial(V). However, no known method is polynomial(V,C) and these papers give NP-hard scenarios where both V and C are made large, e.g. V=2C and make C large, for example. I consider these regimes to be unrealistic and the regime V=large, C=fixed to be realistic. In the "realistic" setting, few or none of the NP-hardness results are valid and there are easy polynomial-time algorithms. This whole area of "research" is largely a "crock." ---- and I would make a stronger statement. In any ranked ballot method the input size is #voters times #alternatives, and any COUNTING method will necessarily be a polynomial function of that value or a smaller value. Even iterative methods for which the number of rounds is indeterminate are upper-bounded by the number of alternatives, which as long as it is finite is always "small". The NP-completeness of the "determine best strategy" derives from the fact that as the alternatives increases, the number of possible ballots exceeds the number of voters. So in general, it is "hard" to determine the effect of changing votes "strategically". But that's a theoretical problem that is completely different from the vote-counting problem. For instance, if there are 10 alternatives there are 9,865,123 possible ranked-ballots (allowing equal rankings and truncation). If there are fewer voters, then pretty much for any method the task of analyzing changes in voters ballots is essentially impossible, but the process of counting the votes cast is something I could do on my laptop in about a second. ---- election-methods mailing list - see http://electorama.com/em for list info