5

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

Turbo
  • 12,812
  • 1
  • 19
  • 68

2 Answers2

5

(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

Community
  • 1
Joshua Grochow
  • 37,260
  • 4
  • 129
  • 228
  • Would you know the complexity of Barvinok (is it $k^{ck}$ as in $\mathsf{LLL}$)? – Turbo Feb 20 '17 at 23:44
  • 1
    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 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? – Turbo Feb 28 '17 at 20:29
  • 1
    @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
  • @JoshuaGrochow May I ask the case what about the promise that it always has exactly $1$ solution? How about finding the solution? – Turbo Feb 28 '17 at 23:36
  • @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 Feb 28 '17 at 23:43
  • @JoshuaGrochow first time I am hearing this class. let me check. – Turbo Feb 28 '17 at 23:47
  • @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 Mar 02 '17 at 00:38
  • @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 Mar 02 '17 at 02:19
  • @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 Mar 02 '17 at 18:37
  • 1
    @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 Mar 02 '17 at 22:28
  • @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 Mar 12 '17 at 01:48
  • @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 Mar 12 '17 at 23:00
  • @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 Mar 13 '17 at 00:47
  • @JoshuaGrochow query is in http://mathoverflow.net/questions/264480/replacing-equalities-with-inequalities-in-fixed-dimension-integer-programming-wi. – Turbo Mar 13 '17 at 20:16
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.

D.W.
  • 12,054
  • 2
  • 34
  • 80
  • 3
    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 00:48