5
$\begingroup$

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

$\endgroup$
5
$\begingroup$

(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

$\endgroup$
  • $\begingroup$ Would you know the complexity of Barvinok (is it $k^{ck}$ as in $\mathsf{LLL}$)? $\endgroup$ – T.... Feb 20 '17 at 23:44
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon Feb 23 '17 at 14:44
  • $\begingroup$ @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? $\endgroup$ – T.... Feb 28 '17 at 20:29
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Feb 28 '17 at 23:32
  • 1
    $\begingroup$ @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. $\endgroup$ – Joshua Grochow Mar 2 '17 at 22:28
5
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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$. $\endgroup$ – Joshua Grochow Feb 21 '17 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.