NAMES:

LOGINS:

PRECEPTS:

COS 226 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 x₁, ..., x_n, are there three distinct integers i, j, and k such that x_i + x_j + x_k = 0.

   3-SUM-PLUS: given n integers x₁, ..., x_n, and an integer b are there three distinct integers i, j, and k such that x_i + x_j + x_k = b.

   
   

   1. 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: x₁, ..., x_n.

      
      
      
      
      
      
      
      
      
      
      
      
      
      
      
      

   2. 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, x₁, ..., x_n.