Confused with the definition of NP

Question

In the blog post at:

Concrete Nonsense

I read:

NP is the set of problems that can be solved by polynomial-time non-deterministic algorithms. An equivalent definition of NP is the set of problems for which a solution can be verified in polynomial time.

Questions:

1) How does the equivalence of the definitions follow?

2) Isn't it possible to verify, in polynomial time, also the solutions of the P class of problems? Namely, given a purported solution, one can calculate the actual solution in polynomial time. Thus, one can verify if it is equal to the purported one in polynomial time. Thus, the 'equivalent definition' above is not just true for NP but also for P, i.e. it is not a definition of NP at all, but just one of its properties.

Am I missing something subtle? I must be, since I have encountered similar 'definitions' of NP class of problems in many different instances.

Answer 1

1) Suppose you have a problem with a polynomially verifiable solution. Then, you can get a non-deterministic polynomial algorithm for that problem simply by guessing a solution (via non-determinism) and verifying it in polynomial time.

Suppose you have a non-deterministic polynomial algorithm. How can we obtain a polynomially verifiable solution (in the literature, this is often called a "certificate" instead of "solution")? Simply take the execution trace of the non-deterministic Turing machine that encodes your algorithm and verify that running that trace through the non-deterministic TM yields the correct result.

2) Yes, it is possible to verify the solutions of problems in P in polynomial time. This only demonstrates that P is a subset of NP. The key difference is that in P, we can construct the solution in deterministic polynomial time. In NP, we only need to verify a solution in deterministic polynomial time. This gap between construction and verification is at the heart of the P vs. NP question. Intuitively, it feels like verification should be strictly easier than construction (and hence NP should be strictly larger than P) but so far we are unable to prove this.

Answer 2

You are missing something somewhat subtle, and you've actually hit on the main point of P vs NP. Every problem in P IS also in NP. This is well known, as if you can solve something in polynomial time, then of course you can verify it, simply by solving it. The P=NP question asks where NP is a subset of P. It's trivial that P is a subset of NP. We question whether there are verifiable problems which are solvable in polynomial time.

I can also take a stab at your first question. A nondeterministic algorithm I'm pretty sure avoids the whole exponential "try all possibilities" problem simply by nondeterministically checking each. So you're simultaneously verifying every possible solution. I could be very wrong here, though, and someone should correct me in the comments.

Answer 3

Non deterministic computers have the ability to choose options randomly yet condition how they choose.

In other words, if you have a search tree for the space of solutions, a non deterministic computer will always select the optimal branch of the tree when computing until it reaches the right leaf (aka a solution to the problem).

To rephrase this differently, NP problems can have the search space of their solutions organized into a tree with polynomially many branches per layer and polynomially many layers given the complexity of the problem.

In P, as far as we know, the problem must have the entire search tree of the set of possible solutions bounded in a size that is polynomial given the size of the input.

So now the question arises, is there always a method to traverse the massive search trees of NP problems in polynomial time, (and can these 'ways' be consistently generated in polynomial time) or are these two classes very distinct.

I think given the visual it's quite clear where most people lean towards: that the two classes are distinct.

Note that your observation is Correct and that the set of trees in P clearly fits the requirements for NP but not vice versa.