**ALL PRINTABLE PDF BOOKS FREE DOWNLOAD** **<<CLICK HERE>>**

**ALL PRINTABLE PDF BOOKS FREE DOWNLOAD** **<<CLICK HERE>>**

## 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?

O(p(n)) | |

O(p( n log n)) | |

O(p(n ^{2})) | |

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?

intractable | |

tractable | |

decision | |

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.

true | |

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?

NP | |

P | |

Hard | |

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?

tractable problems | |

intractable problems | |

undecidable problems | |

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.