PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q5(b)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: Time/Space Complexity; P, NP & NP-Complete

Question

Explain NP-Complete problems.

Solution

Definition, Properties, and Practical Significance of NP-Complete: The class NP-Complete (NPC) comprises the computationally hardest problems in the class NP (Nondeterministic Polynomial time).

A decision problem is defined as NP-Complete if it satisfies two conditions:

  1. : A given candidate solution (certificate) can be verified deterministically in polynomial time .
  2. is NP-Hard: Every problem is polynomial-time reducible to (). That is, an efficient polynomial-time algorithm for would immediately yield a polynomial-time algorithm for every problem in NP.

Cook–Levin Theorem: Proved in 1971 that the Boolean Satisfiability Problem (SAT) is NP-Complete, establishing the foundation of computational complexity theory.

Representative NP-Complete Problems:

Answer:

An NP-Complete problem belongs to NP and is NP-Hard (every problem in NP reduces to it in polynomial time). First proven for SAT by the Cook–Levin Theorem, solving any NP-Complete problem in polynomial time would imply .

All past exam questions for Theory of Computation