This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “P, NP, NP-hard, NP-complete Complexity Classes”.
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))
View Answer
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.
2. Problems that can be solved in polynomial time are known as?
a) intractable
b) tractable
c) decision
d) complete
View Answer
Explanation: Problems that can be solved in polynomial time are known as tractable. Problems that cannot be solved in polynomial time are intractable.
3. The sum and composition of two polynomials are always polynomials.
a) true
b) false
View Answer
Explanation: One of the properties of polynomial functions states that the sum and composition of two polynomials are always polynomials.
4. _________ is the class of decision problems that can be solved by non-deterministic polynomial algorithms.
a) NP
b) P
c) Hard
d) Complete
View Answer
Explanation: NP problems are called as non-deterministic polynomial problems. They are a class of decision problems that can be solved using NP algorithms.
5. Problems that cannot be solved by any algorithm are called?
a) tractable problems
b) intractable problems
c) undecidable problems
d) decidable problems
View Answer
Explanation: Problems cannot be solved by any algorithm are called undecidable problems. Problems that can be solved in polynomial time are called Tractable problems.
6. The Euler’s circuit problem can be solved in?
a) O(N)
b) O( N log N)
c) O(log N)
d) O(N2)
View Answer
Explanation: Mathematically, the run time of Euler’s circuit problem is determined to be O(N2).
7. To which class does the Euler’s circuit problem belong?
a) P class
b) NP class
c) Partition class
d) Complete class
View Answer
Explanation: Euler’s circuit problem can be solved in polynomial time. It can be solved in O(N2).
8. Halting problem is an example for?
a) decidable problem
b) undecidable problem
c) complete problem
d) trackable problem
View Answer
Explanation: Halting problem by Alan Turing cannot be solved by any algorithm. Hence, it is undecidable.
9. How many stages of procedure does a non-deterministic algorithm consist of?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: A non-deterministic algorithm is a two-stage procedure- guessing stage and verification stage.
10. A non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.
a) true
b) false
View Answer
Explanation: One of the properties of NP class problems states that A non-deterministic algorithm is said to be non-deterministic polynomial if the time-efficiency of its verification stage is polynomial.
11. How many conditions have to be met if an NP- complete problem is polynomially reducible?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: A function t that maps all yes instances of decision problems D1 and D2 and t should be computed in polynomial time are the two conditions.
12. To which of the following class does a CNF-satisfiability problem belong?
a) NP class
b) P class
c) NP complete
d) NP hard
View Answer
Explanation: The CNF satisfiability problem belongs to NP complete class. It deals with Boolean expressions.
13. How many steps are required to prove that a decision problem is NP complete?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: First, the problem should be NP. Next, it should be proved that every problem in NP is reducible to the problem in question in polynomial time.
14. Which of the following problems is not NP complete?
a) Hamiltonian circuit
b) Bin packing
c) Partition problem
d) Halting problem
View Answer
Explanation: Hamiltonian circuit, bin packing, partition problems are NP complete problems. Halting problem is an undecidable problem.
15. The choice of polynomial class has led to the development of an extensive theory called ________
a) computational complexity
b) time complexity
c) problem complexity
d) decision complexity
View Answer
Explanation: An extensive theory called computational complexity seeks to classify problems according to their inherent difficulty.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Practice Data Structure MCQ
- Check Design and Analysis of Algorithms Books
- Practice Computer Science MCQs
- Practice Programming MCQs
- Check Programming Books
