Exercises on Reductions  

$20.00

Category:

Description

Exercises on Reductions

1.            Prove that the following two problems have the same complexity by giving a linear-time reductions between the two.

3-SUM: given n integers x1, …, xn, are there three distinct integers i, j, and k such that xi + xj + xk = 0.

3-SUM-PLUS: given n integers x1, …, xn, and an integer b are there three distinct integers i, j, and k such that xi + xj + xk = b.

a.             Give a linear-time reduction from 3-SUM to 3-SUM-PLUS. To demonstrate your reduction, give the 3-SUM-PLUS instance that you would construct to solve the following 3-SUM instance: x1, …, xn.

b.            Give a linear-time reduction from 3-SUM-PLUS to 3-SUM. To demonstrate your reduction, give the 3-SUM instance that you would construct to solve the following 3-SUM-PLUS instance: b, x1, …, xn.