16
$\begingroup$

The decision version of the problem Integar Linear Programming is the following:

  • Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$.
  • Question: is there a matrix $X\in \mathcal{M}_{n,1}(\mathbb{Z})$ such that $AX\leqslant B$? (the inequality being component by component).

This is a well-known $\mathsf{NP}$-complete problem, but I struggle to prove that it is in $\mathsf{NP}$.

An obvious certificate for a positive instance $(A, B)$ would be such a $X$, but there is no guarantee that the size of such an $X$ is polynomial in the size of the input (here, we can consider the size of the instance $(A, B)$ to be $n^2\log_2(\max(|a_{ij}|, |b_i|)$ and the size of $X$ to be $n\log_2(\max |x_i|))$.

What I expect is that if there is such an $X$, there is one with coefficients not too big, but I don't know how to prove this.

While this is a computer science formulation, I am sure that there is some maths behind this to prove the result, so maybe this question should be asked on maths.SE?

This document states:

ILP ∈ NP. (Not obvious! Need a little math to prove it. Proof omitted.)

and this one states:

Unlike with most NP-complete problems, it is not that easy to see that ILP ∈ NP, since a witness need not necessarily have polynomial size. This is the case though, but the reasons are beyond the scope of the course.

But none gives further references.

(Note: I think that this problem is an answer to my previous question)

Improve this question
$\endgroup$

4 Answers 4

Reset to default
19
$\begingroup$

As you have seen in other sources, the proof that there exists a witness with polynomial size does not exactly fit inside the margin, so to speak. The proof I know of (from the book I mention below) depends heavily on the mathematics of linear inequalities and polyhedra, and I expect this to be the case for most proofs. I don't think you will get a deep understanding of the proof without studying the subject first.

This is why, if you wish to know, I suggest you read a book. The book Integer Programming by Conforti, Cornuejols, and Zambelli prove this fact in section 4.8.2 by making use of various results on linear inequalities and polyhedra they covered in earlier chapters. To get the required background for the proof, you should work through chapters 1,3,4. This may take a couple of weeks of your time.

As a very rough sketch of their proof: the idea is that the solution space of a linear program, a polyhedron, can be described in terms of its "boundary": as a combination of a set of vectors called vertices and another set of vectors called (extreme) rays. That is, every point in the solution is equal to the sum of coefficient multiplied by one of these vectors. (with a few more constraints on the coefficients)

It can be shown that we do not need too many of these vectors (this follows from Caratheodory's theorem) and that these vectors have size polynomial in the encoding of the input. Some of the coefficients are already bounded, some are not but can be bounded via the same approach as Meyer's theorem. The combination of these bounds gives a polynomial bound on the size of the solution point.

Improve this answer
$\endgroup$
8
  • 3
    $\begingroup$ @Nathaniel Well, the first paragraph was more intended as an apology than an accusation, though it may not have come across that way. I mostly wanted to stress that (to the best of my knowledge) most CS courses don't cover this because you would have to follow a more specialized course that's usually not in a CS curriculum. $\endgroup$
    – Discrete lizard ♦
    Commented Jan 17 at 20:23
  • 1
    $\begingroup$ I did not take this as an accusation, don't worry. I understand perfectly that such a proof is not covered in a CS course, but I found it unfortunate not to have references to further explainations. $\endgroup$
    – Nathaniel
    Commented Jan 17 at 20:32
  • 1
    $\begingroup$ I tried to understand the proof of the property. After a bit of browsing, I gave up. Here is the dependancy graph of the different theorems and properties necessary to understand the whole proof… i.sstatic.net/AtIew.png $\endgroup$
    – Nathaniel
    Commented Jan 18 at 23:05
  • 1
    $\begingroup$ Elaborating on the rough sketch of proof: Any vertex on the polyhedron of rational solutions to the LP relaxation of the ILP is the solution to a linear equation system with coefficients from the ILP, so it can be expressed exactly using Cramer's rule, and we can bound the number of bits in the numerator and denominator: both are polynomial in the size of the ILP. Hence the same holds for the coordinates of the bounding box of the vertices; if the polyhedron is bounded, we're done. If the polyhedron is unbounded, things get trickier. (Continued) $\endgroup$
    – Lars H
    Commented Jan 20 at 7:28
  • 1
    $\begingroup$ For an unbounded polyhedron, it is possible that the smallest integer point is much farther out than any rational vertex; how much farther depends (informally speaking) on how wide an angle the polyhedron (polyhedral cone?) covers. So this is where the rays enter the picture… (I'm not surprised that needs a ton of machinery to work through.) And having some solution matters. $1 \leqslant 3x_1 - 3x_2 \leqslant 2$ where $x_1,x_2 \geqslant 0$ is rationally feasible, but lacks integer solutions. $\endgroup$
    – Lars H
    Commented Jan 20 at 7:44
5
$\begingroup$

The paper "On the Complexity of Integer Programming" from Papadimitriou has a very compact (2 and a half pages counting from abstract) proof.

It only needs the common knowledge about dual programs and linear algebra, but might be a bit terse.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ I found this paper, but he is solving $AX = B$, not $AX\leqslant B$, which seems to change a whole lot. $\endgroup$
    – Nathaniel
    Commented Jan 19 at 12:06
  • 1
    $\begingroup$ I think there is a problem from the lemma 1: you cannnot use the Cramer's rule for inequalities. Indeed, if $A = I_n$ and $B = 0$, then the vector $X$ with each component equal to $-2^{2^n}$ does not satisfy the result of the lemma, but is still a solution of $AX \leqslant B$. $\endgroup$
    – Nathaniel
    Commented Jan 19 at 18:12
  • $\begingroup$ @Nathaniel But it's not the smallest solution (in 1-norm). Cramer's Rule is, as far as I can see, only used to prove $(a)\Rightarrow (b)$ in Lemma 2. $\endgroup$
    – Sudix
    Commented Jan 19 at 18:22
  • $\begingroup$ Also sorry for deleting my previous comment, was hoping I had deleted it before anybody saw it, because I thought I had seen something I missed after writing it... To restate what I said there: The proof should still work out if one replaces $AX=B$ with $AX\le B$ $\endgroup$
    – Sudix
    Commented Jan 19 at 18:34
  • $\begingroup$ @Nathaniel The difference between $AX=B$ and $AX \leqslant B$ here is just one of the standard reformulations of a linear program. Instead of $AX \leqslant B$ where $X \geqslant 0$, you add slack variables to write the system as $AX + S = B$, where $X,S \geqslant 0$. I was a bit surprised by Papadimitriou's claim that "it is natural to assume $m \leqslant n$", but that is because every equation comes with a slack variable, so his $n$ is $n+m$ from an $AX \leqslant B$ formulation. $\endgroup$
    – Lars H
    Commented Jan 20 at 6:44
2
$\begingroup$

I think there is a reasonably succinct proof in Schrijver (1986) "Theory of Linear and Integer Programming".

Improve this answer
$\endgroup$
-2
$\begingroup$

If I gave you a solution, you would be able to check it in polynomial time. That's what NP means: It is a decision problem, and if the answer is YES, then I can give you information that lets you verify that the answer is YES. Finding that information (in this case: Finding a solution) may be hard.

Also, if there is no solution, I wouln't know what information I could give you that you can check in polynomial time to find that the answer is NO. So unless I (and many very clever people) have missed something, the problem is not in co-NP.

Improve this answer
$\endgroup$
2
  • 6
    $\begingroup$ The problem is that there is no guarantee that the solution has a size polynomial in the size of the input, which is necessary for the problem to be in NP… $\endgroup$
    – Nathaniel
    Commented Jan 17 at 13:02
  • 7
    $\begingroup$ The number of numbers in the solution is polynomial in the size of the input, but the number of digits in each number might not be - that's what has to be proven. $\endgroup$
    – Criticizing Israel not allowed
    Commented Jan 18 at 7:46

Your Answer

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

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