Someone asked me this question and I found I could not answer it even after spending some time re-reading my college textbooks. Specifically, here is the definition of co-NP in many text books:
Definition 1
a problem A is in co-NP if and only if there is a polynomial time procedure V (·, ·) and a polynomial bound p() such that x ∈ A if and only if ∀y : |y| ≤ p(|x|), V (x, y) = 1
Doesn't this mean that if A is in co-NP, then it MUST have a certificate (because every y would be a certificate) and therefore, A is also in NP?
With some thoughts, I am not sure the above definition is correct. Given the following definition of NP:
Definition 2
a decision problem A is in NP if and only if there is a polynomial time procedure V (·, ·) and a polynomial time bound p() such that x ∈ A if and only if ∃y.|y| ≤ p(|x|) ∧ V (x, y) = 1
The straightforward definition for co-NP seems to be:
Definition 3
a decision problem A is in co-NP if and only if there is a polynomial time bound p() such that x ∈ A if and only if ∀y : |y| ≤ p(|x|) there does NOT exist a polynomial time procedure V(.,.) such that V (x, y) = 1
However, Definition 3 is not equivalent to Definition 1, because V(.,.) can be undecidable. Am I missing anything?
Doesn't this mean that if A is in co-NP, then it MUST have a certificate (because every y would be a certificate) and therefore, A is also in NP?
No. V is not a verifier for problem A in the sense of the definition of NP. For V to be a verifier in that sense, we would need to be able to determine x ∈ A by finding a single y such that V(x, y) = 1. With this V, we need to check all possible values of y.
Your proposed "straightforward definition" of co-NP is wrong. For any problem A, we could pick V to be the procedure that ignores its arguments and immediately returns 1. Thus, by your definition, no problems would be in co-NP.