10
$\begingroup$

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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 3
    $\begingroup$ Do you mean that $\alpha$ is strictly increasing, or at least goes to infinity? $\endgroup$
    – Sasho Nikolov
    Apr 30, 2019 at 5:46
  • $\begingroup$ @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? $\endgroup$
    – Turbo
    May 1, 2019 at 3:29
  • $\begingroup$ Added "unbounded" :) $\endgroup$
    – Ryan Williams
    May 11, 2019 at 5:15
  • $\begingroup$ @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 $\endgroup$
    – Ryan Williams
    May 11, 2019 at 5:19

Your Answer

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

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