4
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ Why would the decision variant of ILP not be NP-complete? $\endgroup$
    – Ribz
    Jan 27, 2017 at 19:37
  • 2
    $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Jan 27, 2017 at 21:56
  • $\begingroup$ @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. $\endgroup$
    – Discrete lizard ♦
    Jan 28, 2017 at 9:54
  • $\begingroup$ @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? $\endgroup$
    – Discrete lizard ♦
    Jan 28, 2017 at 13:39

2 Answers 2

Reset to default
5
$\begingroup$

The notion of duality suggested by the discrete Farkas lemma found in Lasserre's paper does not correspond to an integer program. There is a notion of duality for integer programs (see for example here), but strong duality does not hold, so I doubt it can be used along the lines you suggest.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Indeed, the duality in the paper does not do what I think it does. I tried to see if this approach works using the 'normal' Farkas' lemma over the rationals, scaling the resulting LP to the integers. However, then I still have to decide if an inequality that has a rational solution has no integer solutions, so I still need some kind of strong duality for integers (or ILP in P, which means pretty much everything breaks down) $\endgroup$
    – Discrete lizard ♦
    Jan 28, 2017 at 12:48
6
$\begingroup$

The decision problem version of integer linear programming is known to be in NP. In particular, determining whether an integer linear program has a feasible solution is in NP. It is known that if an integer linear program has a feasible solution, then it has a feasible solution whose length (in bits) is at most a polynomial in the length (in bits) of the input. See, e.g., https://cstheory.stackexchange.com/q/34337/5038.

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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