Need clarification regarding certificates of coNP problems

Question

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.

Answer 1

The proof does bot need to be a subset. It might be another indicator that the given set has a some stricture preventing it from being a positive instance of the subsetsums problem. A good example with a non-trivial certificate is linear programming. Linear programs admit both a positive and a negative certificate (For the question whether the optimal can be smaller/greater than a value k). The positive instance is of course an assignment of the variable. The negative however is given by Faraks lemma and the weak duality.

A good exercise for you is to look up linear programs, weak duality and Farkas lemma :)