How to prove P $\subseteq$ NP without machines?

Question

I am trying to understand why P is considered a subset of NP. I don't know the definition of Turing machines yet. Is there a simple way to see why this is true? I have seen some people saying that if a problem is solvable in polynomial time, then it's clearly verifiable in polynomial time, since you can just solve the problem and compare to the solution to be verified. I am not quite convinced, because a problem can have many solutions. Suppose I want to verify a solution to a problem (with many solutions) in P. How is it guaranteed that a polynomial time algorithm will find this solution?

Answer 1

The point is the existence of such a solution to the problem is enough to determine the complexity class of the problem. Although, you can not find that polynomial solution.

Hence, it is just a definition for the complexity classes of $P$ and $NP$.

Answer 2

NP means nondeterministic polynomial time; any polynomial time algorithm is already a nondeterministic polynomial time algorithm, so the inclusion is a trivial one.

---

The "verifier" description is in reference to the following recipe for exploiting nondeterminism:

• Nondeterministically choose between all strings of symbols
• Check if that string of symbols is a solution to the given problem

So if there is any solution that you can verify a solution in polynomial time, it must be generated in polynomial time as well, and so one of the possible execution paths of the above algorithm will discover a solution in polynomial time.