2
$\begingroup$

Suppose we have a 3SUM instance given with the promise that there exists at least one solution. Is the trivial $O(n^2)$ (modulo logarithmic improvements) solution still the best algorithm or is there a sub-quadratic algorithm known?

Improve this question
$\endgroup$
1
  • 7
    $\begingroup$ If an algorithm works with such a promise, then it also works without a promise (we can check in contant time whether solution produced by an algorithm is correct). $\endgroup$
    – Sasha Kozachinskiy
    Mar 31, 2019 at 15:12

0

Reset to default

Your Answer

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