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(n^{2}))

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(N^{2})

View Answer

Explanation: Mathematically, the run time of Euler’s circuit problem is determined to be O(N

^{2}).

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(N

^{2}).

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__.