<p>ETH itself precludes this possibility.</p>

<p>In <a href="https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf" rel="noreferrer">https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf</a>
 we show that any <span class="math-container">$n^{O(1)} n^{k/\alpha(k)}$</span> time algorithm for k-SUM, for any monotone nondecreasing unbounded function <span class="math-container">$\alpha$</span>, would imply ETH is false. </p>

CC BY-SA 4.0
2019-04-30T05:46:12.007Z
Do you mean that $\alpha$ is strictly increasing, or at least goes to infinity?
Sasho Nikolov
CC BY-SA 4.0
2019-05-01T03:29:43.723Z
@RyanWilliams Similar in spirit to ETH like obstruction. Is there anything that would prevent $O((\log n)^{O(k)})$ complexity with polynomial size advice or a PPAD oracle?
Turbo
CC BY-SA 4.0
2019-05-11T05:15:03.233Z
Added "unbounded" :)
Ryan Williams
CC BY-SA 4.0
2019-05-11T05:19:11.133Z
@Brout Note that (log(n))^k is an FPT function, so yeah, ETH rules that out. With poly size advice it would mean subexponential size circuits for 3sat. With a PPAD oracle it would seem to imply that ETH implies PPAD not in P.  To me that would be a breakthrough, I don't know of much corroborating evidence that PPAD isn't in P
Ryan Williams
CC BY-SA 4.0
2019-04-29T20:37:22.427Z
2019-05-11T05:14:30.340Z
2019-05-11T05:14:30.340Z
Ryan Williams
<p>We know under <span class="math-container">$ETH$</span> we cannot solve <span class="math-container">$K$</span>-SUM in <span class="math-container">$f(K)poly(nK)$</span> time under any function <span class="math-container">$f(K)$</span> (usually <span class="math-container">$2^{O(K)}$</span>).</p>

<p>Is there any conjecture that prevents a <span class="math-container">$(\log n)^{O(K)}$</span> complexity (this is entirely consistent with possibility as <span class="math-container">$K=\Omega(n)$</span> we need exponential time for subset sum) or is such possibility allowed?</p>

<cc.complexity-theory><subset-sum>
An obstruction like ETH
Turbo
# An obstruction like ETH

(Asked by: username_0 on 2019-04-29)

We know under $ETH$ we cannot solve $K$-SUM in $f(K)poly(nK)$ time under any function $f(K)$ (usually $2^{O(K)}$).

Is there any conjecture that prevents a $(\log n)^{O(K)}$ complexity (this is entirely consistent with possibility as $K=\Omega(n)$ we need exponential time for subset sum) or is such possibility allowed?

**Tags:** cc.complexity-theory, subset-sum


---

## 1 answers

### Answer by username_1 on 2019-04-29. Score: 16 | Accepted answer

ETH itself precludes this possibility.

In <https://people.csail.mit.edu/rrw/cnf-sat-feasible.pdf>
we show that any $n^{O(1)} n^{k/\alpha(k)}$ time algorithm for k-SUM, for any monotone nondecreasing unbounded function $\alpha$, would imply ETH is false.

> **Comments:**
> **username_2**: Do you mean that $\alpha$ is strictly increasing, or at least goes to infinity?  
> **username_0**: @RyanWilliams Similar in spirit to ETH like obstruction. Is there anything that would prevent $O((\log n)^{O(k)})$ complexity with polynomial size advice or a PPAD oracle?  
> **username_1**: Added "unbounded" :)  
> **username_1**: @Brout Note that (log(n))^k is an FPT function, so yeah, ETH rules that out. With poly size advice it would mean subexponential size circuits for 3sat. With a PPAD oracle it would seem to imply that ETH implies PPAD not in P.  To me that would be a breakthrough, I don't know of much corroborating evidence that PPAD isn't in P  

---

