1. Let A and B be two languages. Assume that we know that A is polynomial- time
ID: 3678278 • Letter: 1
Question
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>: 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.
Explanation / Answer
A is polynomial- time reducible to B, it means that given an instance of AA, there is an algorithm for transforming instances of A into instances of B. A P B.
(a) If B is NP-complete, then so is A
=> True
Since A can be reduced to B in polynomial time and B itself is NP-Complete. therefore A must be NP-Complete.
(b) If A is NP-complete, then so is B
=> False
A is polynomial- time reducible to B, therefore time complexity of B is always less than that of A and it can be anything even polyynomial.
(c) If B is NP-complete and A NP, then A is NP-complete.
=> True
Since A can be reduced to B in polynomial time and B itself is NP-Complete. therefore A must be NP-Complete.
(d) If A is NP-complete and B NP, then B is NP-complete
=> False
A is polynomial- time reducible to B, therefore time complexity of B is always less than that of A and it can be anything even polyynomial.
(e) A and B can't both be NP-complete.
=> False
They both can be NP-complete (if B is NP-Complete, A must be NP-Complete).
(f) If A P, then B P.
=> True
A is polynomial- time reducible to B, therefore time complexity of A is always greater than that of B and A is already a polynomial, B must also be in polynomial.
(g) If B P, then A P.
=> False
A is polynomial- time reducible to B, therefore time complexity of A is always greater than that of B and it can be expononential
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.