<p>(1) As <a href="https://cstheory.stackexchange.com/a/3576/129">finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete</a> (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.</p>

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

<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 <a href="http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf" rel="nofollow noreferrer">author's copy</a>)</p>

<p>[2] FOCS 1993</p>

CC BY-SA 3.0
2017-02-20T23:44:50.603Z
Would you know the complexity of Barvinok (is it $k^{ck}$ as in $\mathsf{LLL}$)?
Turbo
CC BY-SA 3.0
2017-02-23T14:44:10.207Z
Journal version of [2]: http://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
CC BY-SA 3.0
2017-02-28T20:29:53.043Z
@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?
Turbo
CC BY-SA 3.0
2017-02-28T23:32:36.397Z
@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
CC BY-SA 3.0
2017-02-28T23:36:50.760Z
@JoshuaGrochow May I ask the case what about the promise that it always has exactly $1$ solution? How about finding the solution?
Turbo
CC BY-SA 3.0
2017-02-28T23:43:01.753Z
@Turbo: How do you know there's exactly one solution? I ask because maybe your problem is in PPAD, and maybe even PPAD-complete?
Joshua Grochow
CC BY-SA 3.0
2017-02-28T23:47:27.497Z
@JoshuaGrochow first time I am hearing this class. let me check.
Turbo
CC BY-SA 3.0
2017-03-02T00:38:43.300Z
@JoshuaGrochow On some study (may be superficial) it looks like UP does not have a complete problem. So could IP with at most 1 solution be in P or RP without having consequences?
Turbo
CC BY-SA 3.0
2017-03-02T02:19:15.327Z
@Turbo: The lack of UP-complete problems does not prevent problems like UniqueSAT, which are in PromiseUP, from being NP-hard under randomized reductions [Valiant-Vazirani]. (So, in particular, if UniqueSAT was in RP then we would have $\mathsf{NP} \subseteq \mathsf{RP}$.) As I said before, I don't know if the same results hold for "UniqueIP" - might be worth asking a separate question.
Joshua Grochow
CC BY-SA 3.0
2017-03-02T18:37:08.813Z
@JoshuaGrochow sorry I am confused. We think $P=BPP$ which means the reduction from SAT to Unique SAT should be derandomizable. Does that mean then $NP=UP$ is conjectured? Same query goes for any 'randomized' reduction from IP to UniqueIP.
Turbo
CC BY-SA 3.0
2017-03-02T22:28:07.857Z
@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 http://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani (look at both answers!) for details on derandomizing the reduction from SAT to UniqueSAT.
Joshua Grochow
CC BY-SA 3.0
2017-03-12T01:48:37.900Z
@AndrásSalamon the paper here(https://arxiv.org/pdf/1511.00310.pdf) is complexity is $f(n)\cdot L^c$ for some fixed $c>0$ where $L$ is number of input bits and $f(n)$ is doubly exponential $2^{2^{O(n)}}$. If this is the case then should it be $n^{2^{O(d)}}$? My ILP problem has $2$ linear equations in $n$ variables $x_1,\dots,x_n$ with constraints $0\leq x_i\leq M=N^{O(\frac1n)}$ where $0<N<2^{n^{c'}}$ holds for some $c'>1$. Can this integer programming problem be solved in $n^{O(n)}$ arithmetic operations on $O(n)$ sized words?
Turbo
CC BY-SA 3.0
2017-03-12T23:00:57.703Z
@Turbo: Solving 2 (or even poly(n)) linear Diophantine equations can be done easily using, eg, Smith normal form. Solve those, plug in solutions to your original variables, and now you're back to the case where everything is inequalities.
Joshua Grochow
CC BY-SA 3.0
2017-03-13T00:47:51.377Z
@JoshuaGrochow thank you. I am precisely looking for this how to change $=$ to $\leq$ so that I can apply fixed dim IP. Can you please clarify ' Solving 2 (or even poly(n)) linear Diophantine equations can be done easily using, eg, Smith normal form'?
Turbo
CC BY-SA 3.0
2017-03-13T20:16:51.697Z
@JoshuaGrochow query is in http://mathoverflow.net/questions/264480/replacing-equalities-with-inequalities-in-fixed-dimension-integer-programming-wi.
Turbo
CC BY-SA 3.0
2017-02-20T23:32:43.947Z
2017-02-20T23:32:43.947Z
2017-04-13T12:32:28.167Z
Joshua Grochow
<p>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 $&gt; 1$ solutions.  Consequently distinguishing between $\le 1$ solution vs $&gt; 1 $ solution is at least as hard as integer programming itself.</p>

CC BY-SA 3.0
2017-02-21T00:48:02.323Z
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
CC BY-SA 3.0
2017-02-21T00:37:27.900Z
2017-02-21T00:37:27.900Z
D.W.
<p>Integer programming is NP-hard.</p>

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

<p>Integer programming in fixed parameters is P.</p>

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

<np-hardness><big-picture><polynomial-time><integer-programming><fixed-parameter-tractable>
On integer programming
Turbo
# On integer programming

(Asked by: username_0 on 2017-02-20)

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)?

**Tags:** np-hardness, big-picture, polynomial-time, integer-programming, fixed-parameter-tractable


---

## 2 answers

### Answer by username_1 on 2017-02-20. Score: 5 | Accepted answer

(1) As [finding a second satisfying assignment to a 3SAT formula is still $\mathsf{FNP}$-complete](https://cstheory.stackexchange.com/a/3576/129) (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](http://www-imai.is.s.u-tokyo.ac.jp/~yato/data2/SIGAL87-2.pdf))

[2] FOCS 1993

> **Comments:**
> **username_0**: Would you know the complexity of Barvinok (is it $k^{ck}$ as in $\mathsf{LLL}$)?  
> **username_2**: Journal version of [2]: http://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.  
> **username_0**: @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?  
> **username_1**: @username_0: 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.  
> **username_0**: @JoshuaGrochow May I ask the case what about the promise that it always has exactly $1$ solution? How about finding the solution?  
> **username_1**: @username_0: How do you know there's exactly one solution? I ask because maybe your problem is in PPAD, and maybe even PPAD-complete?  
> **username_0**: @JoshuaGrochow first time I am hearing this class. let me check.  
> **username_0**: @JoshuaGrochow On some study (may be superficial) it looks like UP does not have a complete problem. So could IP with at most 1 solution be in P or RP without having consequences?  
> **username_1**: @username_0: The lack of UP-complete problems does not prevent problems like UniqueSAT, which are in PromiseUP, from being NP-hard under randomized reductions [Valiant-Vazirani]. (So, in particular, if UniqueSAT was in RP then we would have $\mathsf{NP} \subseteq \mathsf{RP}$.) As I said before, I don't know if the same results hold for "UniqueIP" - might be worth asking a separate question.  
> **username_0**: @JoshuaGrochow sorry I am confused. We think $P=BPP$ which means the reduction from SAT to Unique SAT should be derandomizable. Does that mean then $NP=UP$ is conjectured? Same query goes for any 'randomized' reduction from IP to UniqueIP.  
> **username_1**: @username_0: 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 http://cstheory.stackexchange.com/questions/7552/derandomizing-valiant-vazirani (look at both answers!) for details on derandomizing the reduction from SAT to UniqueSAT.  
> **username_0**: @AndrásSalamon the paper here(https://arxiv.org/pdf/1511.00310.pdf) is complexity is $f(n)\cdot L^c$ for some fixed $c>0$ where $L$ is number of input bits and $f(n)$ is doubly exponential $2^{2^{O(n)}}$. If this is the case then should it be $n^{2^{O(d)}}$? My ILP problem has $2$ linear equations in $n$ variables $x_1,\dots,x_n$ with constraints $0\leq x_i\leq M=N^{O(\frac1n)}$ where $0<N<2^{n^{c'}}$ holds for some $c'>1$. Can this integer programming problem be solved in $n^{O(n)}$ arithmetic operations on $O(n)$ sized words?  
> **username_1**: @username_0: Solving 2 (or even poly(n)) linear Diophantine equations can be done easily using, eg, Smith normal form. Solve those, plug in solutions to your original variables, and now you're back to the case where everything is inequalities.  
> **username_0**: @JoshuaGrochow thank you. I am precisely looking for this how to change $=$ to $\leq$ so that I can apply fixed dim IP. Can you please clarify ' Solving 2 (or even poly(n)) linear Diophantine equations can be done easily using, eg, Smith normal form'?  
> **username_0**: @JoshuaGrochow query is in http://mathoverflow.net/questions/264480/replacing-equalities-with-inequalities-in-fixed-dimension-integer-programming-wi.  

---

### Answer by username_3 on 2017-02-21. Score: 5

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.

> **Comments:**
> **username_1**: 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$.  

---

