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?

  • 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 '19 at 15:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.