# reduction from 3SUM to 3ARR-ARITH

The 3SUM problem is defined as follows. Given an array A[1...n] of numbers, determine whether there exist $$i,j,k\in \{1,\cdots, n\}$$ so that $$A[i] + A[j]+A[k] = 0$$.

The 3ARR-ARITH problem is defined as follows. Given three arrays $$A[1..n], B[1..n], C[1...n]$$ of numbers, determine whether there exist $$i,j,k \in \{1,\cdots, n\}$$ so that $$B[j] - A[i] = C[k] - B[j].$$

When reducing from problem P1 to problem P2, you assume you have a subroutine that solves problem P2 and use this subroutine to solve P1.

Determine a linear time reduction from 3SUM to 3ARR-ARTIH.

Determine a linear time reduction from 3ARR-ARITH to 3SUM.

I know a linear time reduction from 3ARR-SUM to 3SUM, where 3ARR-SUM is defined as follows: Given three arrays $$A[1...n], B[1...n], C[1...n]$$ of numbers, determine whether there exist $$i,j,k$$ so that $$A[i]+B[j]+C[k] = 0$$.

The reduction can be described by the following algorithm, where 3SUM is a subroutine that solves the 3SUM problem:

3ARR-SUM(A[1...n], B[1...n], C[1...n]):
for i = 1 to n do
X[i] = 10 * A[i] + 2
Y[i] = 10 * B[i] + 4
Z[i] = 10 * C[i] - 6
let A' be an array of 3n 0's
for i = 1 to 3n do
if (i <= n)
A'[i] = X[i]
else if (i <= 2n)
A'[i] = Y[i]
else
A'[i] = Z[i]
if 3SUM(A'[1...3n]) returns (i,j,k) then
sort (i,j,k) so that i <= j <= k
return (i, j - n, k - 2n)


I tried rearranging the expressions for 3SUM and 3ARR-ARITH, but it doesn't seem like that helps. I can't think of something similar to the above either. How would I obtain a single array that 3SUM can solve and for which calling 3SUM on the array will solve 3ARR-ARITH?

Also, I can't seem to figure out how to reduce 3SUM to 3ARR-ARITH. It doesn't seem like defining the arrays A,B,C as follows works: $$A[i] = 10A'[i] + 1, B[j] = 10B'[j] + 2, C[k] = 10C'[k] + 3$$. I have a single array $$A'[1..n]$$ and I want to obtain 3 arrays $$A[1...n], B[1...n], C[1...n]$$ so that if I call 3ARR-ARITH on these 3 arrays, I will get indices $$i,j,k$$ so that $$B[j] - A[i] = C[k] - B[j]$$ and $$A'[i] + A'[j] + A'[k] = 0.$$

• Where did you encounter this? We require that you attribute the source of all copied material. Please see our guidelines and edit your question accordingly: cs.stackexchange.com/help/referencing. I notice that I've given you this feedback before: cs.stackexchange.com/questions/140827/…
– D.W.
Commented Jan 13, 2022 at 7:44
• Please don't delete your question after you have received an answer. Part of our mission is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future, and answerers may be answering on that basis, so deleting the question after someone answers can potentially be viewed as impolite to whoever takes time to answer.
– D.W.
Commented Jan 14, 2022 at 8:15
• Cross-posted: stackoverflow.com/q/70691591/781723. Please do not post the same question on multiple sites.
– D.W.
Commented Jan 14, 2022 at 8:20

Let's rewrite the pattern we're looking for in 3ARR-ARITH: $$A[i] - 2B[j] + C[k] = 0.$$ This should suggest a simple reduction from 3SUM to 3ARR-ARITH, and another simple reduction from 3ARR-ARITH to 3ARR-SUM, which combined with the reduction you mention, results in a reduction from 3ARR-ARITH to 3SUM.