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

DOWNLOAD FREE PDF <<CLICK HERE>>

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

Congratulations - you have completed P, NP, NP-hard, NP-complete Complexity Classes Multiple choice Questions and Answers.

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%


Your answers are highlighted below.
Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions 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 MCQ multiple objective type questions 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 MCQ multiple objective type questions 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 MCQ multiple objective type questions 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 MCQ multiple objective type questions 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.

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results
There are 5 questions to complete.

DOWNLOAD FREE PDF <<CLICK HERE>>