Monday, August 09, 2010

P != NP

A paper purports to prove that P != NP. Any of my mathematical readers care to comment?

(via Bruce Schneier)


  1. I can't comment on the proof itself, having given up on math after having the most boring Group Theory professor in the entire universe (picture every possible stereotype of a boring professor put together) as an undergraduate, but I suspect that a universe in which P = NP would not have such a hearty enforcement of Murphy's Law as ours. Life just isn't as easy as P = NP suggests; there is no algorithmic Big Rock Candy Mountain.

  2. I think everyone agrees that P = NP is intuitively implausible.

  3. Scott Aaronson has a nice post regarding the issue here: Not very technical, but has links to some other technical points.


Please pick a handle or moniker for your comment. It's much easier to address someone by a name or pseudonym than simply "hey you". I have the option of requiring a "hard" identity, but I don't want to turn that on... yet.

With few exceptions, I will not respond or reply to anonymous comments, and I may delete them. I keep a copy of all comments; if you want the text of your comment to repost with something vaguely resembling an identity, email me.

No spam, pr0n, commercial advertising, insanity, lies, repetition or off-topic comments. Creationists, Global Warming deniers, anti-vaxers, Randians, and Libertarians are automatically presumed to be idiots; Christians and Muslims might get the benefit of the doubt, if I'm in a good mood.

See the Debate Flowchart for some basic rules.

Sourced factual corrections are always published and acknowledged.

I will respond or not respond to comments as the mood takes me. See my latest comment policy for details. I am not a pseudonomous-American: my real name is Larry.

Comments may be moderated from time to time. When I do moderate comments, anonymous comments are far more likely to be rejected.

I've already answered some typical comments.

I have jqMath enabled for the blog. If you have a dollar sign (\$) in your comment, put a \\ in front of it: \\\$, unless you want to include a formula in your comment.