250+ TOP MCQs on P, NP, NP-hard, NP-complete Complexity Classes and Answers

Data Structures & Algorithms Multiple Choice Questions 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(n²))
d) O(p(m log n))
View Answer

Answer: a
Clarification: 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

Answer: b
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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

Answer: c
Clarification: 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(N²)

Answer: d
Clarification: Mathematically, the run time of Euler’s circuit problem is determined to be O(N²).

7. To which class does the Euler’s circuit problem belong?
a) P class
b) NP class
c) Partition class
d) Complete class

Answer: a
Clarification: Euler’s circuit problem can be solved in polynomial time. It can be solved in O(N²).

8. Halting problem is an example for?
a) decidable problem
b) undecidable problem
c) complete problem
d) trackable problem

Answer: b
Clarification: 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
Answer: b
Clarification: 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

Answer: a
Clarification: 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
Answer: b
Clarification: 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

Answer: c
Clarification: 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

Answer: b
Clarification: 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

Answer: d
Clarification: 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
Answer: a
Clarification: An extensive theory called computational complexity seeks to classify problems according to their inherent difficulty.

contest