22
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Warren Schudy Oct 20 '10 at 12:51
  • 4
    $\begingroup$ 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. $\endgroup$ – Warren Schudy Oct 20 '10 at 12:53
  • 1
    $\begingroup$ to be horribly pedantic, we might only need a semigroup. $\endgroup$ – Suresh Venkat Oct 20 '10 at 17:11
11
$\begingroup$

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$.)

$\endgroup$
  • 1
    $\begingroup$ Haven't you reduced to 3MUL mod a prime rather than 3MUL? It may be that $ab=c \pmod(p)$ but $ab \ne c$. $\endgroup$ – Warren Schudy Oct 20 '10 at 21:21
  • 1
    $\begingroup$ Yes, as is, this is a reduction to 3MUL mod p. Good point. $\endgroup$ – virgi Oct 20 '10 at 23:52
  • $\begingroup$ 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? $\endgroup$ – Markus Jalsenius Oct 21 '10 at 10:59
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Warren Schudy Oct 20 '10 at 13:18
  • 1
    $\begingroup$ The equation doesn't seem correct ( try x and y = 2.1 ). Could you clarify what you meant? $\endgroup$ – Raphael Oct 23 '10 at 19:12

Your Answer

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

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