# Why do P-class problems not require a witness like NP?

If I am given a problem in P, to claim that I have solved it, I would need to give proof, right? For example, to show a number is not prime, if I use some deterministic algorithm, I can return the prime factors of that number.

I am finding it weird that P does not require a witness/certificate in the definition like NP.

• Maybe because the algorithms used in P class problems are deterministic, and assuming the algorithm is correct, we will not need a witness. Also, maybe P does not include witness because implicitly if we can solve it in polynomial time, the verifier can also check and generate their own witness in polynomial time. – WeCanBeFriends Jun 19 '19 at 21:41

A language $$L$$ is in $$\mathsf{NP}$$ if for any input $$x \in L$$, you can find a witness, of polynomial in $$|x|$$ size, that can be checked in polynomial time. This is, "$$x \in L$$! Here is a proof, that you can verify in polynomial time."
A language $$L$$ is in $$\mathsf{P}$$ if for any input $$x \in L$$, you can find a witness, of size $$1$$, that can be checked in polynomial time. This is, "$$x \in L$$! I do not give you a proof, but you can find one yourself in polynomial time."