Polynomial time reductions MCQs

By: Prof. Dr. Fazal Rehman | Last updated: September 23, 2024

Polynomial Time Reductions MCQs What does it mean for a problem A to be polynomial-time reducible to problem B? A) Problem A can be solved faster than problem B. B) There exists an algorithm that solves problem A using a polynomial number of steps relative to the size of problem B. C) Problem A is easier than problem B. D) Problem A can only be solved using a non-deterministic Turing machine. Answer: B A polynomial-time reduction from problem A to problem B implies that: A) Problem A can be solved in polynomial time. B) Problem B can be solved in polynomial time if problem A can be solved in polynomial time. C) Problem A and problem B are equivalent. D) Problem A and problem B are NP-complete. Answer: B Which of the following statements is true about polynomial-time reductions? A) They are always one-to-one mappings between problems. B) They allow transformation of problems in exponential time. C) They are transitive; if A is reducible to B and B is reducible to C, then A is reducible to C. D) They only apply to problems in the class P. Answer: C If problem A is NP-complete and problem A is polynomial-time reducible to problem B, then: A) Problem B is also NP-complete. B) Problem B is in P. C) Problem B is in NP. D) Problem B is in NP-hard. Answer: D A problem A is said to be NP-hard if: A) It can be solved in non-deterministic polynomial time. B) It is at least as hard as any problem in NP. C) It can be solved using a deterministic Turing machine. D) It can be solved in logarithmic time. Answer: B Which of the following is an example of a polynomial-time reduction? A) Transforming an NP-hard problem to a P problem. B) Transforming a problem in NP to a problem in P. C) Transforming an NP-complete problem to an NP-hard problem. D) Transforming an NP problem to an NP-complete problem. Answer: B The concept of polynomial-time reductions is primarily used to: A) Compare the efficiency of algorithms. B) Determine whether a problem is in NP. C) Prove the hardness of problems. D) Classify problems as NP-complete. Answer: C A polynomial-time reduction between two problems A and B implies that: A) Problem A is easier than problem B. B) Problem B is easier than problem A. C) Problem A and problem B are equivalent in terms of computational complexity. D) Problem A is in NP. Answer: C If problem A can be polynomial-time reduced to problem B, and problem B is in P, then: A) Problem A is in P. B) Problem A is in NP. C) Problem A is NP-complete. D) Problem A is NP-hard. Answer: A A polynomial-time reduction from problem A to problem B typically involves: A) A mapping that runs in polynomial time. B) A transformation that converts problem A to problem B using exponential time. C) A deterministic Turing machine that solves both problems simultaneously. D) A non-deterministic Turing machine that decides whether problem A reduces to problem B. Answer: A  
All Copyrights Reserved 2025 Reserved by T4Tutorials