Just thought I’d mention that Scott Aaronson has a post on his blog about “proofs that should finish with a gong […] instead of a QED symbol”. Theorem 2 is IMO the most ridiculous of them all, giving an explicit algorithm for any NP-complete problem that runs in polynomial time if P=NP (!).

Advertisements