P, NP, NP-hard, NP-complete Complexity Classes Multiple Choice Questions and Answers (MCQs)

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))

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

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

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

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

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)

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

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

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

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

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

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

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

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

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

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!