- Theory of Automata MCQs
- Finite Automata MCQs
- Regular Languages
- Context-Free Grammars (CFG)
- Pushdown Automata (PDA) MCQs
- Context-Free Languages MCQs
- Turing Machines MCQs
- Decidability and Undecidability MCQs
- Computational Complexity MCQs
- Advanced Topics in Automata Theory
- Applications of Automata Theory MCQs
Polynomial time reductions MCQs
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