1. Let A and B be two languages. Assume that we know that A is polynomial- time reducible to B. Which of the following can we conclude from this? (Circle all that apply.) Explain your answers with one or two sentences.

(a) If B is NP-complete, then so is A.

(b) If A is NP-complete, then so is B.

(c) If B is NP-complete and A NP, then A is NP-complete.

(d) If A is NP-complete and B NP, then B is NP-complete.

(e) A and B can't both be NP-complete.

(f) If A P, then B P.

(g) If B P, then A P.

2. The Factoring Language is dened to be {: x,k {0,1}* (both binary numbers) and there exists a nontrivial factor of x that is k}.

It is common knowledge that if you can determine an algorithm that efficiently determines string membership in the Factoring Language, then you can break common cryptography systems like RSA. Explain why the Factoring Problem is in NP.