# 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 at 21:41

## 2 Answers

If we look at decision problems, then a problem is in P if for "YES" instances "I think the answer is YES" is a witness that can be checked in polynomial time :-)

• If I understand correctly; the fact that we have a "YES" from a deterministic algorithm serves as witness? – WeCanBeFriends Jun 19 at 22:45

This is basically a maybe more succinct version of gansher729's answer.

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."

• What is the witness? afaik, the witness should give you proof that the word is in the language. Simply saying that it is, would not count as a witness, as there is no proof that you ran the algorithm to begin with, right? – WeCanBeFriends Jun 20 at 11:35
• To get a proof, you need a witness plus polynomial time. Many problems, especially NP complete problems, you need a good witness. For problems in P, you can find a proof in polynomial time. You can take any statement, no matter how clever or nonsensical, call it a witness, and witness plus polynomial time effort will get you a proof. You can completely ignore the witness because the problem is in P anyway. – gnasher729 Jun 20 at 21:25