3
$\begingroup$

Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space.

Is there any consequence if it can be done in $k^{O(k^\alpha)}$ time and $O(k^c)$ space for some $\alpha\in(0,1)$ under the assumption the integer programming problem we have had at most $1$ solution?

$\endgroup$

1 Answer 1

7
$\begingroup$

An instance of CNF-SAT with $k$ variables can easily be written as a 0/1 integer linear program over the same variable set, since a clause such as $x_1 \vee x_3 \vee \neg x_4 \vee \neg x_6$ naturally corresponds to a constraint $x_1 + x_3 + (1-x_4) + (1-x_6) \geq 1$, when all variables are forced to take values $0$ and $1$.

Hence if integer programming in $k$ variables can be solved in time $k^{O(k^\alpha)}$ for some $\alpha < 1$, then CNF-SAT with arbitrarily long clauses can be solved in $k^{O(k^\alpha)} = 2^{O(k^\alpha \cdot \log k)}$, which would contradict the Strong Exponential Time Hypothesis since $c \cdot k^\alpha \cdot \log k < k$ for any constant $c$, $\alpha < 1$, and sufficiently large $k$.

$\endgroup$
5
  • 1
    $\begingroup$ I'm guessing you mean the ETH, rather than the SETH here? $\endgroup$
    – daniello
    Mar 7, 2017 at 11:05
  • 2
    $\begingroup$ @BartJansen I am looking for problems with unique solution. $\endgroup$
    – Turbo
    Mar 7, 2017 at 17:40
  • $\begingroup$ @Turbo under randomized reductions, Unique k-SAT (the promise problem where there is 0 or 1 solution) has the same exponential time complexity as k-SAT. So an algorithm as described above for ILP with 0 or 1 feasible solutions would refute (randomized) ETH. (See The complexity of Unique k-SAT: An Isolation Lemma for k-CNFs, Calabro et al.) $\endgroup$
    – daniello
    Mar 8, 2017 at 8:03
  • $\begingroup$ @daniello : ​ I thought only the as-k-goes-to-infinity version of that was known. ​ ​ ​ ​ $\endgroup$
    – user6973
    Mar 8, 2017 at 15:11
  • 1
    $\begingroup$ @Ricky Demer Yes, the statement is that for every k and $\epsilon$, there is a k' such a $c^n$ time algorithm for unique k'-SAT leads to a $c^{n(1+\epsilon)}$ time algorithm for k-SAT. Set k=3 and let $\epsilon$ tend to 0 to get the ILP consequence. $\endgroup$
    – daniello
    Mar 8, 2017 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.