Lower time bounds for integer programming with two variables (Q1072938): Difference between revisions

Any integer programming problem is reformulated as the following recognition problem: Given a set of m linear inequalities, \[ \sum^{n}_{i=1}a_{ij}x_ i\leq b_ j\quad (j=1,2,...,m),\quad a_{ij},\quad b_ j\in Q \] (Q is the set of rationals), determine whether there is a solution \(x=(x_ 1,...,x_ n)\in Z^ n\) which fulfills all of them (where Z is the set of integers). This problem is well known to be NP-complete. A simple version of the integer programming problem with \(n=2\), \(m=3\) is discussed. In this case the problem reduces to deciding whether a given triangle in the plane contains a point with integer coordinates. At first, the authors define a problem with only one variable which can be reduced in constant time to their integer programming problem. Next it is proved that there exists an algorithm for the one-dimensional problem which works in time polynomial in the binary length p of the input. As a result, two lower bounds are shown for the number of operations necessary to solve the integer problem: (i) \(\Omega\) (p) steps are necessary if operations from \(\{+,-,\div,\leq \}\) are admissible, and (ii) \(\Omega\) (log p) steps are necessary if operations from \(\{+,-,(\cdot),\leq \}\) are admissible where (\(\cdot)\) denotes the floor function, i.e., (x) is the largest integer smaller or equal to x. New techniques are necessary for relating the bounds to the length of the input and for handling the floor function which prevents us from applying the well-known algebraic arguments. The best known algorithm is due to H. W. Lenstra, jun. and needs O(p) steps over \(\{+,-,*,\div,(\cdot),\leq \}\).