Time complexity classes (P, NP, NP-complete, NP-hard) MCQs

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

Time Complexity Classes MCQs
Which time complexity class represents the set of problems solvable in polynomial time on a deterministic Turing machine?

A) P
B) NP
C) NP-complete
D) NP-hard
Answer: A

The class NP stands for:

A) Non-Polynomial
B) Non-Polynomial Deterministic
C) Non-deterministic Polynomial
D) Non-deterministic Exponential
Answer: C

A problem is in NP if:

A) It can be solved in exponential time.
B) It can be solved in logarithmic time.
C) Its solution can be verified in polynomial time.
D) Its solution can be verified in constant time.
Answer: C

A problem is NP-complete if:

A) It is the hardest problem in NP.
B) It can be solved in polynomial time.
C) It has no known solution.
D) It is easier than problems in P.
Answer: A

Which of the following is true about NP-complete problems?

A) They can be solved in polynomial time.
B) They can be solved using non-deterministic Turing machines.
C) They are always easier than problems in P.
D) They are at least as hard as any problem in NP.
Answer: D

The class NP-hard consists of problems that are:

A) At least as hard as any problem in NP.
B) Easier than problems in P.
C) Solvable in logarithmic time.
D) Deterministic polynomial time solvable.
Answer: A

Which of the following is not a property of problems in P?

A) They can be solved in polynomial time.
B) Their solutions can be verified in polynomial time.
C) They are generally easier than problems in NP.
D) They can be solved using a deterministic Turing machine.
Answer: C

A problem is NP if:

A) It can be solved using a deterministic Turing machine in polynomial time.
B) Its solution can be verified in polynomial time on a non-deterministic Turing machine.
C) It can be solved in exponential time.
D) It is equivalent to an NP-complete problem.
Answer: B

Which class contains all problems that are as hard as the hardest problems in NP, but may not be in NP themselves?

A) P
B) NP
C) NP-complete
D) NP-hard
Answer: D

If a problem is NP-complete, it implies that:

A) It can be solved in polynomial time.
B) It is the easiest problem in NP.
C) It is at least as hard as any problem in NP.
D) Its solution can be verified in constant time.
Answer: C

 

Related Posts: