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

 

 Help authour, Buy PDF Ebook   >>>Click Here<<<

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))
Economics Questions answers

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
EVS Questions answers

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
Reading comprehension Questions answers

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
Aptitude test Questions answers

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
Data interpretation (DI) Questions answers

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.

 

 Download all FREE PDF Ebook >>>CLICK HERE<<<