patternMinor
Does integer programming $\in$ NP imply $NP=CoNP$?
Viewed 0 times
implyconpprogrammingdoesinteger
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#69398, answer score: 6
Revisions (0)
No revisions yet.