[ck113]

From the article: "Another interesting feature of NP problems is that a solution can be checked in polynomial time by a deterministic Turing machine. So, checking a solution of a NP problem is a P problem."

That's not just an interesting feature of NP problems, it's an alternate definition. You can define NP as the class of problems that have polynomial-time "verifiers". That is, the class of problems for which, given a candidate solution, you can determine in polynomial time whether that solution is correct.

Examples: given a proposed assignment to the variables of a boolean formula, you can check in P-time whether that assignment satisfies the formula. Given a proposed route through a set of cities, you can check in polynomial time whether that route has length less than K. Given a set S of integers, a subset of S, and a target T, you can check in P-time whether that subset sums up to T. Etc.

I find the "polynomial time verifier" definition of NP to be much clearer than the "solvable by a polynomial-time nondeterministic Turing machine" definition. They're exactly equivalent -- I don't know why the latter is so much more common.

[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.

[philwelch]

The "polynomial-time nondeterministic Turing machine" explanation has the following strengths:

1. It explains where the "N" in "NP" comes from and why.

2. For someone learning P and NP towards the end of an automata theory class, where nondeterminism and NFA-DFA transformations have already been introduced, it seems like a more elegant and meaningful development of the concept.

[rw]

The nondeterministic characterization is easier to work with.

[nopassrecover]

Verifying that length is less than K and verifying that length is the shortest possible route are two different questions. Can someone clarify how the travelling salesman problem is NP-Complete (i.e. how does it have a P verification?)

[philwelch]

There's a bit of confusion here. Saying the traveling salesman problem is NP-complete means more than simply it has a P verification. Saying the traveling salesman problem is in NP implies it has a P verification. But saying that it is NP-complete implies that, in addition to being in NP, any other NP problem can be (deterministic-polynomially) translated into it.

[ck113]

It's mostly just a technicality of the definition. NP (and P for that matter) can only contain "decision problems," i.e., problems for which the answer must be Yes or No.

So the NP formulation of the Traveling Salesman problem is "does this graph admit a route of length less than K?" For any constant K, that's an NP-complete problem.