P and NP Factoring, the decomposition of a natural number into prime factors, is
ID: 653964 • Letter: P
Question
P and NP
Factoring, the decomposition of a natural number into prime factors, is believed to be a difficult problem. It is not a decision problem, but it is equivalent to the following decision problem L. L = { (m, k) m and k are positive integers written in binary such that m has no prime divisor less than or equal to k}. First, we want to see that L is equivalent to factoring. Then we are interested in the complexity of L. (a) Assume factoring is doable in polynomial time. Show that this implies L to be in P. (b) Assume L is in P. Show how to factor any positive integer n in polynomial time under this assumption. (c) Show that L E -NP. (d) Show that L E NP.Explanation / Answer
properties of polynomials- Suppose that f(X) ? K[X] is a monic polynomial. I.e., f(X) = X n + an?1X n?1 +
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.