# On integer programming

Integer programming is NP-hard.

What is the status of integer programming problem that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ category)?

Integer programming in fixed parameters is P.

What is the status of integer programming problem in fixed parameters that decides between existence of $\leq1$ solution and $>1$ solutions (note $0$ solutions falls in $\leq1$ category)?

(1) As finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete (indeed, it is $\mathsf{ASP}$-complete, see Theorem 3.5 of [1]), and we can encode 3SAT as an integer program by a parsimonious reduction, finding a second integer point in an integer program is also $\mathsf{NP}$-hard.

(2) Barvinok [2] showed that in fixed dimension, you can actually count the number of integer points in polynomial time, so the answer to your second question is $\mathsf{P}$.

[1] Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003. (freely available author's copy)

[2] FOCS 1993

• Would you know the complexity of Barvinok (is it $k^{ck}$ as in $\mathsf{LLL}$)? – T.... Feb 20 '17 at 23:44
• Journal version of [2]: dx.doi.org/10.1287/moor.19.4.769 claims $n^{O(d)}$ time, where $n$ is the size of the input and $d$ is the dimension, though the paper itself only seems to discuss an algorithm that takes $n^{O(d^2)}$ time. – András Salamon Feb 23 '17 at 14:44
• @AndrásSalamon Thank you. Suppose we have a promise integer programming problem with promise that it has either $1$ solution or $0$ solution - is the problem NP complete? What if coefficients are all non-negative and the solution also has non-negative coordinates? – T.... Feb 28 '17 at 20:29
• @Turbo: IP with the promise of 1 or 0 solutions is in PromiseUP (basically by definition), so is unlikely to be NP-complete. (Technically: it's a promise problem so it's not in NP, but what I'm saying is it's unlikely to be NP-hard.) However, by analogy with SAT, it may nonetheless be NP-hard under randomized reductions, though it's not clear to me whether one can use a version of the isolation lemma for IP. – Joshua Grochow Feb 28 '17 at 23:32
• @Turbo: No, not necessarily. Note that $P=BPP$ does not necessarily mean that $P^X = BPP^X$ for all functions $X$. More generally, a collapse of language classes doesn't necessarily imply a collapse of the corresponding kinds of reductions. See cstheory.stackexchange.com/questions/7552/… (look at both answers!) for details on derandomizing the reduction from SAT to UniqueSAT. – Joshua Grochow Mar 2 '17 at 22:28

It's NP-hard. Given an integer programming problem $P$, add an irrelevant variable $z$ with no constraints; call the resulting problem $P'$. Now if $P$ has no solutions, then $P'$ has no solutions; if $P$ has a solution, then $P'$ has $> 1$ solutions. Consequently distinguishing between $\le 1$ solution vs $> 1$ solution is at least as hard as integer programming itself.

• And if you want the polytope to stay bounded you can even add in the constraint $0 \leq z \leq 1$, then the number of solutions to $P'$ is twice that of $P$, so it is either 0 or $> 1$. – Joshua Grochow Feb 21 '17 at 0:48