2

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.

Tony
  • 455
  • (2) Yes, ever $P$ problem is an $NP$ problem. The key question is whether every $NP$ problem is also a $P$ problem. The second statement is true for $P$ problems, but possibly true for other problems as well. – Thomas Andrews Jun 17 '14 at 12:53

3 Answers3

1

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.

gregkow
  • 853
  • My problem with calling the above 'definition' is the following: Say we have a set of red apples. They may or may not have a worm inside, we don't know. Then we want to define those that don't have a worm by stating that they are red. – Tony Jun 17 '14 at 03:41
  • 1
    The reason it can be a good definition is that even though it is true for things in the P class, that only makes sense as P is a subset of NP. Moreover, it is an if and only if statement. All NP problems can be verified in polynomial time, and all problems that can be verified in polynomial time are in NP. As it's an if and only if, there is no compelling reason for it not to be a definition. – gregkow Jun 17 '14 at 22:19
  • To respond to the apple example, this illustrates the key difference. An apple is not red if and only if it doesn't have a worm, as those with worms are also red. The definition works only because it is necessary and sufficient. – gregkow Jun 17 '14 at 22:20
1

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.

Sidharth Ghoshal
  • 16,771
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.

mhum
  • 2,447
  • I would have a hard time understanding this answer without the one from gregcow and especially the one from frogeyedpeas, so picking it as the answer wasn't an easy choice. But there can be only one. I selected this one because it gives more details on how does the second definition follow from the first. – Tony Jun 17 '14 at 23:54