# P, NP, NP-hard, NP-complete Complexity Classes Multiple choice Questions and Answers

## Click on any option to know the CORRECT ANSWERS

 Question 1
The worst-case efficiency of solving a problem in polynomial time is?
 A O(p(n)) B O(p( n log n)) C O(p(n2)) D O(p(m log n))

Question 1 Explanation:
The worst-case efficiency of solving an problem in polynomial time is O(p(n)) where p(n) is the polynomial time of input size.

 Question 2
Problems that can be solved in polynomial time are known as?
 A intractable B tractable C decision D complete

Question 2 Explanation:
Problems that can be solved in polynomial time are known as tractable. Problems that cannot be solved in polynomial time are intractable.

 Question 3
The sum and composition of two polynomials are always polynomials.
 A true B false

Question 3 Explanation:
One of the properties of polynomial functions states that the sum and composition of two polynomials are always polynomials.

 Question 4
..... is the class of decision problems that can be solved by non-deterministic polynomial algorithms?
 A NP B P C Hard D Complete

Question 4 Explanation:
NP problems are called as non-deterministic polynomial problems. They are a class of decision problems that can be solved using NP algorithms.

 Question 5
Problems that cannot be solved by any algorithm are called?
 A tractable problems B intractable problems C undecidable problems D decidable problems