[emtel]

I skimmed this paper and it seems to be exceptionally bad. The proof sketch offered is that a winning strategy can be verified quickly, but finding a winning strategy requires searching over 3^n possible strategies.

But this assumes that brute force is the only possible way to find a winning strategy, and thus proves far too much. A similar argument would prove that sorting is NP hard, if you start by the assumption that the only way to sort data is by trying every possible permutation.

I may be wrong, but I'm pretty sure any time you claim to have a proof that a problem is NP complete, but your proof doesn't include a reduction, you're doing it wrong.

(The paper does offer what it calls a reduction to 3-sat , but it's completely hand-wavy, and I can't even understand the intuition behind it at all.)