Edit made on June 15, 2025 by ColinWright at 15:07:55
Deleted text in red /
Inserted text in green
WM
HEADERS_END
Prev: What is NP? / Next: What does it mean to say Problem A is harder than Problem B?
----
*Theorem:*
Any problem *A* that's in time complexity class $P$ _
is also in class $NP.$
[[[>50 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.
In fact, if we stick to "Decision Problems" where the answer is
always just "Yes" or "No", then we're OK. The technical part is
to show that every problem that requires an answer can be cast
as a decision problem.
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.$
----
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?