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.
Multiplicative version of 3-SUM
cc.complexity theory;ds.algorithms;time complexity