<p>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.</p>

<p>Consider any triple of integers $a,b,c$ in the new set $S'$.
The number of prime divisors of any nonzero $ab-c$ is $&lt;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$.</p>

<p>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)$}.</p>

<p>(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$.)</p>

CC BY-SA 2.5
2010-10-20T21:21:52.950Z
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
CC BY-SA 2.5
2010-10-20T23:52:45.447Z
Yes, as is, this is a reduction to 3MUL mod p. Good point.
virgi
CC BY-SA 2.5
2010-10-21T10:59:36.410Z
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
CC BY-SA 2.5
2010-10-20T19:54:46.937Z
2010-10-20T19:54:46.937Z
virgi
<p>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.</p>

CC BY-SA 2.5
2010-10-20T13:18:08.137Z
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
CC BY-SA 2.5
2010-10-23T19:12:12.203Z
The equation doesn't seem correct ( try x and y = 2.1 ). Could you clarify what you meant?
Simd
CC BY-SA 2.5
2010-10-20T12:59:31.543Z
2010-10-20T12:59:31.543Z
Warren Schudy
<p>What is known about the time complexity of the following problem, which we call 3-MUL?</p>

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

<p>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?</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-20T12:51:02.493Z
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
CC BY-SA 2.5
2010-10-20T12:53:45.747Z
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
CC BY-SA 2.5
2010-10-20T17:11:28.130Z
to be horribly pedantic, we might only need a semigroup.
Suresh Venkat
<cc.complexity-theory><ds.algorithms><time-complexity>
Multiplicative version of 3-SUM
Markus Jalsenius
# Multiplicative version of 3-SUM

(Asked by: username_0 on 2010-10-20)

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.

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_2**: to be horribly pedantic, we might only need a semigroup.  

---

## 2 answers

### Answer by username_3 on 2010-10-20. Score: 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$.)

> **Comments:**
> **username_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$.  
> **username_3**: Yes, as is, this is a reduction to 3MUL mod p. Good point.  
> **username_0**: 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?  

---

### Answer by username_1 on 2010-10-20. Score: 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.

> **Comments:**
> **username_1**: 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$.  
> **username_4**: The equation doesn't seem correct ( try x and y = 2.1 ). Could you clarify what you meant?  

---

