# Does integer programming $\in$ NP imply $NP=CoNP$?

Although it is relatively simple to see that integer linear programming is NP-hard, whether it lies in NP is a bit harder. Therefore, I'm wondering whether the following reasoning shows that $ILP\in NP$ implies $NP=CoNP$.

To be precise, I am considering the decision variant of ILP over a non-unary input encoding, so the problem is: given an integer matrix $A$; an integer vector $b$, does there exist an integer vector $y \in Z_n$ with $Ay \leq b$?

The main issue here is that if we take such an $y$ as NP-certificate, it might be of exponential size in terms of the input, but this of course does not mean a certificate cannot exist.

My idea was that if we assume ILP in NP, we can use a discrete version of the Farkas lemma (see here) to transform an ILP instance with the answer NO to an ILP instance with the answer YES, which then would imply that ILP is in coNP. So we get an NP-complete problem in coNP, which implies that $NP=coNP$. Since most people think $NP\neq coNP$, this is 'evidence' for ILP not being in NP.

However, I'm not sure if my reasoning is correct. In particular, does this 'discrete Farkas lemma' work in polynomial time and create an ILP of polynomial size of the original one?

• Why would the decision variant of ILP not be NP-complete?
– Ribz
Commented Jan 27, 2017 at 19:37
• Have you read the paper you link to? It probably answers your question. As this is hardly a standard result, most people answering this question will likely have to read the paper; but it makes more sense for you to do it. Commented Jan 27, 2017 at 21:56
• @Riebuoz It is not entirely trivial, as the 'obvious' certificate, the vector $y$ might be exponential in the size of the input $A$, $b$, where a certificate must be of polynomial size. Commented Jan 28, 2017 at 9:54
• @Riebuoz Actually, the first claim is my conclusion upon reading this source, but as D.W. stated in the answer, decision ILP is in NP. Does this mean that the referenced post is answered incorrectly? Commented Jan 28, 2017 at 13:39

Consequently, it is unlikely that "integer programming $\in$ NP implies NP=CoNP". If it did (and you found a proof of that fact), you would have found a proof that NP=CoNP.