22

What is known about the time complexity of the following problem, which we call 3-MUL?

Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$?

This problem is similar to the 3-SUM problem, which asks whether there are three elements $a,b,c\in S$ such that $a+b+c=0$ (or equivalently $a+b=c$). 3-SUM is conjectured to require roughly quadratic time in $n$. Is there a similar conjecture for 3-MUL? Specifically is 3-MUL known to be 3-SUM hard?

Note, the time complexity should apply in a "reasonable" model of computation. For instance, we could reduce from 3-SUM on a set $S$ to 3-MUL on set the $S'$, where $S'=\{2^x\mid x\in S\}$. Then a solution to 3-MUL, $2^a\cdot 2^b=2^c$, exists if and only if $a+b=c$. However, this exponential blow-up of the numbers scales very badly with various models, like the RAM model for example.

Markus Jalsenius
  • 321
  • 1
  • 2
  • Your reduction does show that 3-MULT is 3-SUM hard if the input numbers can be expressed using exponential (a.k.a. scientific) notation. – Warren Schudy Oct 20 '10 at 12:51
  • 4
    Any algorithm for 3-SUM that relies solely on the fact that addition is a group can be translated into an algorithm for 3-MULT, and vice versa. Any algorithm separating the two would therefore need to do something unusual with the numbers. – Warren Schudy Oct 20 '10 at 12:53
  • 1
    to be horribly pedantic, we might only need a semigroup. – Suresh Venkat Oct 20 '10 at 17:11

2 Answers2

11

Your reduction from $3$SUM to $3$MUL works with a minor standard modification. Suppose your original integers were in {$1,\ldots,M$}. After the transformation $x\rightarrow 2^x$ the new integers are in {$2,\ldots,2^M$}. We will reduce the range.

Consider any triple of integers $a,b,c$ in the new set $S'$. The number of prime divisors of any nonzero $ab-c$ is $<2M$. The number of such triples is $n^3$. Hence the number of primes $q$ which divide at least one of the $ab-c$ nonzero numbers is at most $2Mn^3$.

Let $P$ be the set of the first $2M\cdot n^4$ primes. The largest such prime is of size at most $O(Mn^4\log Mn)$. Pick a random prime $p\in P$. With high probability $p$ will not divide any of the nonzero $ab-c$, so we can represent each $a\in S'$ by its residue, mod $p$, and if $3$MUL finds some $ab=c$ in $S'$, with high probability it will be correct for the original $3$SUM instance. We have reduced the range of the numbers to {$0,\ldots, O(Mn^4\log Mn)$}.

(This is a standard size reduction. You might be able to do better by considering the fact that the $ab-c$ are always differences of two powers of $2$.)

virgi
  • 2,489
  • 19
  • 25
  • 1
    Haven't you reduced to 3MUL mod a prime rather than 3MUL? It may be that $ab=c \pmod(p)$ but $ab \ne c$. – Warren Schudy Oct 20 '10 at 21:21
  • 1
    Yes, as is, this is a reduction to 3MUL mod p. Good point. – virgi Oct 20 '10 at 23:52
  • This is a very interesting approach. However, we are particularly interested in a deterministic reduction from 3-SUM to 3-MUL. Would it perhaps be possible to derandomise the size reduction technique? – Markus Jalsenius Oct 21 '10 at 10:59
3

Have you tried the reduction $S'=\{2^{x/M}|x\in S\}$ where $M=\max S− \min S$? The results are real numbers so you'd have to round to some number of digits. To ensure that the numbers add correctly despite the rounding you may need to add a bit of random noise.

Warren Schudy
  • 1,874
  • 16
  • 15
  • Oops, random noise doesn't seem sufficient to fix the rounding error. However these ideas do seem promising for reducing the other way to show 3-MULT is no harder than 3-SUM, since e.g. $(\lceil x \rceil + 1) + \lceil y \rceil = \lceil x + y \rceil + 1$. – Warren Schudy Oct 20 '10 at 13:18
  • 1
    The equation doesn't seem correct ( try x and y = 2.1 ). Could you clarify what you meant? – Simd Oct 23 '10 at 19:12