<p>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$.</p>

<p>Hence if integer programming in $k$ variables can be solved in time $k^{O(k^\alpha)}$ for some $\alpha &lt; 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 &lt; k$ for any constant $c$, $\alpha &lt; 1$, and sufficiently large $k$.</p>

CC BY-SA 3.0
2017-03-07T11:05:49.907Z
I'm guessing you mean the ETH, rather than the SETH here?
daniello
CC BY-SA 3.0
2017-03-07T17:40:49.010Z
@BartJansen I am looking for problems with unique solution.
Turbo
CC BY-SA 3.0
2017-03-08T08:03:17.097Z
@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.)
daniello
CC BY-SA 3.0
2017-03-08T18:41:38.310Z
@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.
daniello
CC BY-SA 3.0
2017-03-07T10:10:18.173Z
2017-03-07T10:10:18.173Z
Bart Jansen
<p>Integer programming in $k$ variables can be done in $k^{O(k)}$ time and $O(k^c)$ space.</p>

<p>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?</p>

<cc.complexity-theory><big-picture><integer-programming><fixed-parameter-tractable><exp-time-algorithms>
Consequences of faster parameterized integer programming
Turbo
# Consequences of faster parameterized integer programming

(Asked by: username_0 on 2017-03-07)

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?

**Tags:** cc.complexity-theory, big-picture, integer-programming, fixed-parameter-tractable, exp-time-algorithms

---

## 1 answers

### Answer by username_1 on 2017-03-07. Score: 7 | Accepted answer

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$.

> **Comments:**
> **username_2**: I'm guessing you mean the ETH, rather than the SETH here?  
> **username_0**: @BartJansen I am looking for problems with unique solution.  
> **username_2**: @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.)  
> **username_2**: @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.  

---

