P Problems Are In NP

AllPages RecentChanges Links to this page Edit this page Search Entry portal Advice For New Users

Any problem A that's in time complexity class P
is also in class NP.

There are some technical points here (surprise surprise). Firstly, we need to know that there is only one solution, and in fact that's usually not the case. There are ways around that, but we need to pay attention to them. Secondly, the checking itself takes time, but the size of the solution and alleged solution must be polynomial, because we can't generate anything super-polynomial in polynomial time. Checking should probably be linear in the size of the solution, and the sum of two polynomials is again a polynomial. So we're OK.

Proof:

Take any problem A that's in class P. We want to show that it's in NP, and to do that we need to show that any alleged solution to a given instance can be checked in polynomial time.

So consider an instance I and an alleged solution S. We need to show that S can be checked in polynomial time.

But A is in P, so we can actually solve it in polynomial time. So solve it (taking polynomial time) and then check the real solution against the alleged solution. That tells us whether the alleged solution is valid.

Thus we have checked the alleged solution, and it's taken us only polynomial time. Hence A is in NP.