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?

$\endgroup$

1 Answer 1

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.

$\endgroup$
4
  • 3
    $\begingroup$ Do you mean that $\alpha$ is strictly increasing, or at least goes to infinity? $\endgroup$ Commented 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
    Commented May 1, 2019 at 3:29
  • $\begingroup$ Added "unbounded" :) $\endgroup$ Commented 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$ Commented May 11, 2019 at 5:19

Your Answer

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

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