P Problems Are In NP

Links to this page
Edit this page
Entry portal
Advice For New Users

Prev: What is NP? / Next: What does it mean to say Problem A is harder than Problem B?

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.


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.

So the collection of all P problems is contained within the collection of all NP problems. Next we go further and talk about the comparative difficulty of problems.
Prev: What is NP? / Next: What does it mean to say Problem A is harder than Problem B?
Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout