19
Apr
Proof of P != NP:
Proof by contradiction. Assume P = NP. Let y be a proof that P = NP. The proof y can be verified in polynomial time by a competent computer scientist, the existence of which we assert. However, since P = NP, the proof y can be generated in polynomial time by such computer scientists. Since this generation has not yet occurred (despite attempts by such computer scientists to produce a proof), we have a contradiction.
10:11 on April 19th, 2005
Yo dude, it would make this blog a lot more useful if you actually pick categories, and optionally format your post!
15:24 on April 19th, 2005
OK, I edited the post.
21:07 on April 19th, 2005
You stole Hubie Chen’s proof. (I worked with him a bit back in the Cornell days.)
21:11 on April 19th, 2005
I just wanted to write a post. Man. You guys are harsh. I’ll never post on this ever again. EVER. :’(
:’(
14:10 on April 21st, 2005
(This post comes late as I only just happened to register etc.)
Doesn’t this argument depend on what the exponent in the polynomial time is
Perhaps computer scientists have not been working on P vs NP long enough to find a proof….
17:51 on April 22nd, 2005
Ha… to follow up on Shuchi’s comment (and to intentionally depress Luis)… how are we quantifying over “all” efficient algorithms by quantifying over all researchers? If we could make this move, it seems that all possible (ptime) algorithms papers would have already been written?