1
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 19, 2019 at 21:41

2 Answers 2

1
$\begingroup$

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 :-)

$\endgroup$
1
  • $\begingroup$ If I understand correctly; the fact that we have a "YES" from a deterministic algorithm serves as witness? $\endgroup$ Jun 19, 2019 at 22:45
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jun 20, 2019 at 11:35
  • 1
    $\begingroup$ 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. $\endgroup$
    – gnasher729
    Jun 20, 2019 at 21:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.