Editing PProblemsAreInNP
You are currently not logged in.
To change this, fill in the following fields:
Username
Password
Who can read this page?
The World
Members
Council
Admin
You have been granted an edit lock on this page
until Thu Apr 25 20:56:32 2024.
Press
to finish editing.
Who can edit this page?
The World
Members
Council
Admin
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. 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?