Polynomial time reductions MCQs

By: Prof. Dr. Fazal Rehman Shamil | 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

 

Related Posts: