# Need clarification regarding certificates of coNP problems

NOTE: this is not an attempt to prove $$NP \neq coNP$$

There is one thing I have never been able to completely digest about the certificates of problems in $$coNP$$ and I would very much appreciate a definitive clarification from this community.

Let's focus on the subset sum problem ($$SUBSUM$$), now we all know that this problem is in $$NP$$ since, to accept language membership, a Prover $$P_v$$ can emit a certificate which a verifier $$V_r$$ can check in polynomial time. Up to here no problem. The complement of this problem ($$\overline{SUBSUM}$$) is in $$coNP$$ which means that we do not know if there is a succinct (ie polynomial) certificate to decide the language. If such a certificate does not exist, then $$NP \neq coNP$$ and therefore $$P \neq NP$$. What I don't understand is this:

If I have (for example) a set $$S$$ of integers and the number $$0$$ as an input and I ask: Prove me that $$\forall s \in S \space\space\lnot SUBSUM$$, ie $$\nexists$$ a subset of $$S$$ such that the sum of its element give $$0$$ as a result (this is $$\overline{SUBSUM}$$, the complement of the subset problem). How can a certificate exist for this problem whose verification is in $$P$$? I mean, i need to prove it for all the subset so the search space must be the powerset of $$S$$. If $$|S|=n$$ then $$\mathcal{|P(S)|}=2^n$$. So if the prover, for example, produce a $$2^{n/3}$$ certificate, this means that I systematically leave out $$2^{ \frac{2}{3}n}$$ subsets. What I don't completely understand and for which I need clarification is why this argument is not accepted as evidence that $$NP$$ is not closed under complement.

• Thanks for your kindly reply. So, in order to prove $NP \neq coNP$, we need to prove that there is no indicator that the given set has some structure preventing it from being a positive instance, right? Dec 3 '19 at 14:39