1
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Yamar69 Dec 3 '19 at 14:39
  • $\begingroup$ Yes exactly. The difficulty comes from the freedom we have in the choice of the certificate. $\endgroup$ – narek Bojikian Dec 3 '19 at 18:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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