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

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

 Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
..... 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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
Problems that cannot be solved by any algorithm are called?
 A tractable problems B intractable problems C undecidable problems D decidable problems
Question 5 Explanation:
Problems cannot be solved by any algorithm are called undecidable problems. Problems that can be solved in polynomial time are called Tractable problems.

There are 5 questions to complete.