16

In his answer to this question, John Feminella says:

It's possible to do this sub-quadratically if you get really fancy, by representing each integer as a bit vector and performing a fast Fourier transform, but that's beyond the scope of this answer.

What is the asymptotically optimal way of solving the problem described in that question?

Community
  • 1
  • 1
Yktula
  • 14,179
  • 14
  • 48
  • 71

1 Answers1

13

Suppose we have an array 1 2 4. We represent this array as a polynomial f(x) = x^1 + x^2 + x^4. Let's look at f(x)^2, which is

x^2 + 2 x^3 + x^4 + 2 x^5 + 2 x^6 + x^8

The number of ways to write n as the sum of two elements of the array is the coefficient of x^n, and this is true in general. FFT gives us a way to multiply polynomials efficiently*, so basically what we do is compute f(x)^3 and look at the coefficient of the target number S.

  • The reason this algorithm doesn't solve the 3SUM problem is that the efficiency of an FFT multiply depends on the degree of the resulting polynomial and thus that the array values lie in a small range.
Adam Wagner
  • 15,469
  • 7
  • 52
  • 66
foo
  • 131
  • 2
  • f(x)^3 has O(n^3) coefficients. Will the FFT allow you to compute a useful subset of the coefficients? – Tom Sirgedas Jul 15 '11 at 01:47
  • 2
    It seems like this would **detect** whether three numbers summed to a given target, but it wouldn't **find** what those three numbers are. Am I mistaken about this? – templatetypedef Jul 15 '11 at 01:48
  • @Tom It's only a win when the range is small and thus f(x)^3 has degree <<< n^2. – foo Jul 15 '11 at 01:50
  • @templatetypedef You're right. It's possible to call this as a subroutine O(log n) times to figure out what the numbers are. – foo Jul 15 '11 at 01:51
  • @foo- How exactly would you do this? I don't see what these calls would look like. – templatetypedef Jul 15 '11 at 02:09
  • @templatetypedef A simple randomized strategy would be to try subsequences where each element is included independently with probability 1/2. The three target elements are all included with constant probability, and in expectation a constant fraction of the others go away. I'm confident this can be derandomized but don't have a cite offhand. – foo Jul 15 '11 at 02:30
  • @templatetypedef See this on how to recover the solution. http://cstheory.stackexchange.com/questions/32036/finding-witness-in-minkowski-sum-of-integers/32196 – Chao Xu Aug 05 '15 at 21:58