# On false proofs of P=NP, or how not to use induction

The power set of an $n$-set has $2^n$ elements. This isn’t that complicated. However, mimicking some proofs purporting to show P=NP, I can (incorrectly!) show that the power set grows polynomially in $n$. Heck, I could even show that the power set has a constant number of elements.

Proof. It is not hard to see that the number $T(n)$ of elements of the power set of an $n$-set satisfies the recurrence $T(n)=2T(n-1)$. I’d like to claim that $T(n)$ grows polynomially in $n$. In the base case $T(1)=2$. Good so far. Now for the inductive step, suppose that the number of elements of the power set is polynomial for $n$. Then $T(n+1)=2T(n)=2n^{O(1)}=(n+1)^{O(1)}$.  QED.

Of course there’s a huge problem in that proof, but that hasn’t stopped others from publishing essentially the same thing. For example, see A polynomial-time algorithm for the maximum clique problem. For those looking to find mistakes in purported P versus NP proofs, here’s a treasure trove.