[ck113]

Ooh! Ooh! I just remembered another cool thing about the "polynomial-time verifier" formulation of NP. It makes it possible to phrase the P vs. NP question much more starkly.

The standard formulation of P vs. NP is something like "do deterministic polynomial-time Turning machines have the same power as nondeterministic polynomial-time Turing machines?" A deep question, but not a very snappy sentence.

But the alternate formulation is something like: "is it always as easy to find a correct answer as it is to check if a given answer is correct?" Really brings home why it seems so painfully obvious that P is not equal to NP (of course it's easier to check an answer than to find one), and makes it seem that much more profoundly strange that we haven't found a way to prove this.

[zck]

I have a problem with this way of thinking about NP. Just because it's "harder" to find an answer doesn't mean it can't be in P. Maybe it's just n^127 to find the answer, but n^2 to verify. I don't think it's so obvious that P!=NP as you say it is.

Also, being as that it's not proven, you wouldn't want to teach that it's "so painfully obvious that P is not equal to NP" in a classroom.

[ck113]

Sure, of course. I'm not out to convince anyone that P != NP here, especially not using Proof By Obviousness. I just meant to underline one of the intuitions that makes so many people believe they must be different.

Also, like so many terms in computer science, "harder" has different meanings in different subspecialities. To a complexity theorist, a problem that takes O(n^127) time to solve is not any harder than one that takes O(n) to solve -- they're both in the same hardness class. Just one of the many warpings in perspective that staring too long at P and NP can give you.