Homework 20

Consider the following algorithm, which correctly solves the Bandersnatch

(BS) problem using a solution to the JubJub (JJ) problem:

Input: data: array of positive integers

Input: n: size of data

Output: Bandersnatch(data)

1 Algorithm: BandersnatchReduction

2 Sort data

3 for i = 1 to n do

4 if JubJub(data) then

5 data[i] = data[n − i] − data[i]

6 else

7 data[i] = data[i] · data[n − i]

8 end

9 Sort data

10 end

11 return data

1. Suppose that BS is NP-Hard and JJ ∈ P. Prove that P = NP or explain

why BandersnatchReduction does not prove P = NP.

2. Suppose that BS ∈ P and JJ is NP-Hard. Prove that P = NP or explain

why BandersnatchReduction does not prove P = NP.

1

## Reviews

There are no reviews yet.