Complexity Classes in Data Structure And Algorithm : Practice MCQ Questions & Answers with Explanations

Computational complexity theory seeks to classify problems according to their inherent difficulty based on the resources required to solve them.

Hamiltonian circuit, bin packing, and partition problems are NP-complete. The Halting problem is undecidable — it cannot be solved by any algorithm at all.

Two steps: first, show the problem is in NP; second, prove that every NP problem is polynomially reducible to it.

The CNF satisfiability problem belongs to the NP-complete class. It deals with Boolean expressions in conjunctive normal form.

Two conditions must be met: a function t that maps all yes-instances of decision problems D1 to D2, and t must be computable in polynomial time.

A non-deterministic algorithm is classified as NP if its verification stage runs in polynomial time.

A non-deterministic algorithm is a two-stage procedure: a guessing stage and a verification stage.

The Halting problem, proved by Alan Turing, cannot be solved by any algorithm and is therefore undecidable.

Euler's circuit problem can be solved in polynomial time O(N^2), so it belongs to the P class.

The Euler's circuit problem has a running time of O(N^2).

Problems that cannot be solved by any algorithm are called undecidable problems. Problems solvable in polynomial time are called tractable.

NP (Non-deterministic Polynomial) is the class of decision problems solvable by non-deterministic polynomial algorithms.

One of the fundamental properties of polynomial functions states that both the sum and composition of two polynomials always result in a polynomial.

Problems solvable in polynomial time are called tractable. Problems that cannot be solved in polynomial time are called intractable.

The worst-case efficiency of solving a problem in polynomial time is O(p(n)), where p(n) is a polynomial function of the input size n.