Problem 1. Prove that if NP = BPP, then the polynomial hierarchy collapses to the second
level; namely PH = Σ2.
Problem 2. Prove that BPP = coBPP (i.e., show that for all f 2 BPP, 1 − f 2 BPP).
Problem 3. Let f0; f1 : f0; 1g∗ ! f0; 1g be two functions, and let f : f0; 1g∗ ! f0; 1g be the
‘OR’ function defined by f(x) = f0(x) _ f1(x).
a. (5 pts) Show that if f0; f1 2 NP, then f 2 NP.
b. (5 pts) Suppose that f0(x) = 0 whenever the first bit of x is a 1, and f1(x) = 0 whenever
the first bit of x is a 0. Suppose, moreover, that f0 is NP−hard. Prove that f is NP−hard.
Define the subset-sum function fSS : f0; 1g∗ ! f0; 1g which takes a list of integers (x1; : : : ; xn; s)
as input and outputs 1 if there exists a subset T ⊂ f1; : : : ; ng such that s = Pi2T xi, and outputs
0 if not. In this part, you will prove that fSS is NP−hard, via a reduction from 3SAT. Your
reduction will contain two parts. Define the intermediate function fint : f0; 1g∗ ! f0; 1g which
takes as input:
• a list of strings y1; : : : ; yn 2 f0; 1gm such that for all α = 1; : : : ; m:
#i 2 f1; : : : ; ng : yi(α) = 1 ≤ 5;
where yi(α) denotes the α−th bit of yi;
• a value r 2 f0; 1; 2; 3gm;
and outputs 1 iff there exists T ⊂ f1; : : : ; ng such that for all α = 1; : : : ; m: Pi2T yi(α) = r(α).
Problem 4. Prove that fint ≤ fSS.
Thus, in order to prove that fSS is NP−hard, it will suffice to prove that f3SAT ≤ fint (where
f3SAT takes as input a 3CNF formula Φ and outputs 1 iff Φ is satisfiable). Here is the algorithmic
part of the reduction from f3SAT to fint; problem 5 below asks you to complete the analysis.
Input: The reduction takes a 3CNF formula Φ with variables fx1; : : : ; xng and clauses f’1; : : : ; ’mg.
Output: The reduction will output the value s 2 f0; 1; 2; 3gm+n, and additionally it outputs
2n + 2m strings:
A1; : : : ; An; B1; : : : ; Bn; C1; : : : ; Cm; D1; : : : ; Dm 2 f0; 1gn+m:
The Computation: The value s and the strings are computed as follows:
· s = (1; : : : ; 1; 3; : : : ; 3); the first n coordinates are all 1 and the final m are all 3;
· Ai(i) = 1; Ai(’) = 1 if ’ includes the literal xi
· Bi(i) = 1; Bi(’) = 1 if ’ includes the literal x_i
· Cj(’) = 1 if ’ is the j−th clause of Φ
· Dj(’) = 1 if ’ is the j−th clause of Φ
In the computation bullets where we defined the strings, we have only specified the bits which
are 1; all unspecified bits are assumed to be 0. Furthermore, we are using a non-standard but
convenient notation for the indices of the strings. For a string x 2 f0; 1gn+m we write x(i) for
the i−th bit (for i = 1; : : : ; n). This is more-or-less normal. However, if ’ is the j−th clause of
Φ (j = 1; : : : ; m), we write x(’) for the (n + j)−th bit of x. Notice that for each i = 1; : : : ; n,
only Ai and Bi have 1s in the i−th bit, all other strings have 0s; additionally, for the j−th clause
’ of Φ, there are only 5 strings whose (n + j)−th bit is 1, Cj and Dj and the 3 literals which
appear in ’. Thus, the output of the reduction is a valid input into fint.
Problem 5. Prove that Φ is satisfiable if and only if fint evaluates the output of the reduction
(on input Φ) to 1.