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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s