Theory of NP-Completeness: Concepts, Certificate Checks and a Worked Reduction

Learn what P, NP, NP-hard and NP-complete mean. Verify a clique certificate, then follow a complete 3-SAT to CLIQUE reduction with both proof directions.

KnowledgeGate Team

Exam prep & CS education

Updated 19 Nov 20265 min read
Theory of NP-Completeness: Concepts, Certificate Checks and a Worked Reduction

P, NP, NP-hard and NP-complete blur together when a proof demands a certificate, the right reduction direction and both halves of an if-and-only-if argument. A size-3 clique can be verified, and a three-clause 3-SAT instance can be reduced to a nine-vertex CLIQUE instance with its assignment recovered.

NP-completeness begins with decision problems and polynomial time

A decision problem outputs yes or no. CLIQUE(G,k) asks whether G has a clique of size at least k; finding the largest clique is the optimisation version. These classes use the decision form.

Class

Meaning

P

Decision problems solvable in polynomial time by a deterministic algorithm

NP

Decision problems whose yes instances have certificates verifiable in polynomial time

NP-hard

Problems to which every problem in NP reduces in polynomial time; membership in NP is not required

NP-complete

Problems that are both in NP and NP-hard

P is a subset of NP, and whether P = NP remains unknown. A polynomial-time algorithm for one NP-complete problem would solve every problem in NP in polynomial time. NP means nondeterministic polynomial time, not "non-polynomial". The GATE CS Exam Preparation category connects Algorithms and Theory of Computation.

NP certificate verification: a size-3 CLIQUE

A size-3 CLIQUE certificate passes three pair checks, while S'={A,D,E} fails because two edges are absent.

Take V={A,B,C,D,E}, E={{A,B},{A,C},{B,C},{B,D},{C,D},{D,E}} and k=3. For S={A,B,C}, all 3 choose 2 = 3 pairs, {A,B}, {A,C} and {B,C}, are in E, so the verifier accepts.

For S'={A,D,E}, {D,E} exists, but {A,D} and {A,E} do not, so it rejects. Generally, check |S|=k, then every unordered pair. An adjacency matrix needs k(k-1)/2 lookups, or O(k^2). This proves only that CLIQUE is in NP.

An NP-completeness proof has two obligations

To prove target problem B is NP-complete:

  1. Show B is in NP with a certificate and polynomial-time verifier.

  2. Map known NP-complete problem A to B in polynomial time, proving x is yes for A if and only if f(x) is yes for B.

The direction is A <=p B: a solver for B could solve hard source A after conversion. Reducing B to A does not make B hard. The conversion must be polynomial, but need not find an assignment or clique.

Worked reduction from 3-SAT to CLIQUE

Let

phi=(x OR y OR NOT z) AND (NOT x OR z OR w) AND (NOT y OR NOT w OR z).

Call the clauses C1, C2, C3 and set k=m=3. Make one vertex per literal occurrence:

  • C1:x, C1:y, C1:NOT z

  • C2:NOT x, C2:z, C2:w

  • C3:NOT y, C3:NOT w, C3:z

Connect cross-clause vertices whose literals are not complements. Add no edges within clauses. Between C1 and C2, the 9 possible pairs lose (x,NOT x) and (NOT z,z), leaving 7 edges. Between C1 and C3, remove (y,NOT y) and (NOT z,z), leaving 7. Between C2 and C3, remove (w,NOT w), leaving 8. Result: 9 vertices and 7+7+8=22 edges.

K={C1:x,C2:z,C3:NOT w} is a clique. Its vertices come from distinct clauses, and x, z, NOT w are pairwise consistent, so all three edges exist. The assignment x=True, y=False, z=True, w=False satisfies every clause. For graph terminology, see Graph Theory: Euler, Hamiltonian, Coloring for GATE CS.

Three-column literal graph for the sample formula, with red crosses on complement pairs and a blue triangle marking the size-3 clique.

Why the 3-SAT-to-CLIQUE reduction works

If phi is satisfiable, choose one true literal from each clause. The vertices are in different clause columns, and no two selected literals are complements. Every pair is connected, so they form an m-clique.

Conversely, an m-clique has at most one vertex from each clause because same-clause vertices lack edges. Exactly m vertices select one literal per clause. Complements cannot both appear because their edge is omitted, so the selections extend to a satisfying assignment.

For m three-literal clauses, the construction makes 3m vertices and at most 9m(m-1)/2 edges. This is O(m^2). CLIQUE is in NP, and 3-SAT reduces to it in polynomial time, so CLIQUE is NP-complete.

NP-completeness exam questions: rapid checks

The issued GATE 2026 CS syllabus names asymptotic complexity and greedy, dynamic programming and divide-and-conquer under Algorithms, and undecidability under Theory of Computation. It does not name P, NP or NP-completeness, so treat these as concept checks, not a claim about marks or frequency.

  • A problem in P is also in NP: true.

  • A problem proved NP-hard but not proved in NP is NP-complete: false.

  • 3-SAT <=p X and X in NP prove X NP-complete: true.

  • X <=p 3-SAT alone proves X NP-hard: false.

Dynamic Programming Explained: 0/1 Knapsack teaches a polynomial-time method for a specific recurrence. NP-completeness classifies decision problems through reductions. Turing Machines and Decidability Explained asks whether a problem is computable at all. Hard, slow and undecidable are not synonyms.

NP-completeness traps and corrections

  • Trap: NP problems cannot be solved in polynomial time. Correction: P is contained in NP; whether every NP problem is in P is unknown.

  • Trap: Showing a target is in NP finishes the proof. Correction: hardness still needs a correctly directed reduction from a known NP-complete problem.

  • Trap: Using an optimisation problem in a decision-class proof. Correction: state the threshold form first, such as "is there a clique of size at least 3?"

  • Trap: A reduction gives both problems the same running time. Correction: it transfers yes/no solvability with polynomial overhead, not identical algorithms.

Theory of NP-completeness in the short version

Checklist: use a decision problem; state the certificate; bound its verifier; reduce a known hard source to the target; prove both directions and bound the construction.

Here S={A,B,C} passes three edge checks. The formula gives 9 vertices, 22 edges and k=3; its highlighted clique gives x=True, y=False, z=True, w=False. Use GATE Guidance by Sanchit Sir for complexity, algorithms and theory in a structured CS sequence.

Self-test for psi=(a OR b OR c) AND (NOT a OR b OR d): find the vertex count and k. Which candidate, {C1:a,C2:b} or {C1:a,C2:NOT a}, forms a clique?

Answer: 6 vertices and k=2. {C1:a,C2:b} is a 2-clique; {C1:a,C2:NOT a} is not an edge because the literals conflict.