# Can Lenstra's algorithm output all feasible solutions in O^*(f(k)) time where k is the number of variables and f is a computable function in k?

It is well-known that Lenstra's famous algorithm (presented in the paper Integer programming with a fixed number of variables) can solve an ILP problem in $O^*(f(k))$ time where k is the number of variables occur in the ILP.

My question is that whether the algorithm or any of its improved versions can output all feasible solutions in $O^*(f(k))$ time?

• What does $O^*$ mean? See also this answer to a related question. Mar 22, 2013 at 18:16
• The $O^*$ notation usually ignores polynomial factors in the instance size. Mar 22, 2013 at 22:10

## 1 Answer

No. The number of feasible solutions cannot be upper bounded by $f(k)n^{O(1)}$.

Consider the integer program $I_n: 1 \le x\le 2^n$ with the integer variable $x$. So, $k=1$ and the program can be described with $O(n)$ bits. But it has $2^n$ solutions, which is exponential in the instance size.