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.
