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$
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$
  • 1
    $\begingroup$ I'm guessing you mean the ETH, rather than the SETH here? $\endgroup$ – daniello Mar 7 '17 at 11:05
  • 2
    $\begingroup$ @BartJansen I am looking for problems with unique solution. $\endgroup$ – T.... Mar 7 '17 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 '17 at 8:03
  • $\begingroup$ @daniello : ​ I thought only the as-k-goes-to-infinity version of that was known. ​ ​ ​ ​ $\endgroup$ – user6973 Mar 8 '17 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 '17 at 18:41

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.