The Exam Blueprint: Module 4 PYQ Deep Analysis (2022–2024)

An analysis of 8 exam questions spanning 2022 to 2024 reveals that Module 4 is short but incredibly predictable. It has the tightest scope of any module. The question asking to define P, NP, NP-Complete, and NP-Hard has appeared in every single paper.

Complete PYQ Table (8 Questions)

Total marks tracked: 38 marks across 3 years.

---

Topic Heat Map

(Note: Some topics overlap with MCQs).

---

The 2 Guaranteed Question Types

1. 🔴 The "Big Four" Complexity Classes (7M) Appeared in ALL 3 years. You must formally define P, NP, NP-Complete, and NP-Hard, and draw the standard Euler diagram showing their assumed relationship (assuming $P \neq NP$).

2. 🟠 Reductions and Cook's Theorem (7M) Started appearing heavily in 2024. You must be able to state Cook's Theorem ("SAT is NP-Complete") and explain the mechanism of polynomial-time reductions.

The Critical Proofs & Reductions

---

Concept 1: Cook's Theorem

Statement: The Boolean Satisfiability Problem (SAT) is NP-Complete.

Why is it foundational? Before Cook's Theorem (proven by Stephen Cook in 1971), to prove a problem was NP-Complete, one would theoretically have to prove that every single problem in NP could be reduced to it. Cook proved that any non-deterministic Turing machine computation can be encoded as a Boolean formula. By proving that SAT is NP-Complete, Cook provided the first NP-Complete problem. From then on, to prove a new problem $X$ is NP-Complete, we only need to reduce SAT (or another known NP-Complete problem) to $X$. It kickstarted the entire field of computational complexity.

---

Concept 2: The Logic of Polynomial-Time Reductions

What is it? A polynomial-time reduction from Problem A to Problem B (written as $A \le_p B$) is an algorithm that transforms any instance of A into an instance of B in polynomial time, such that the answer to A is "YES" if and only if the answer to B is "YES".

How is it used to prove NP-Completeness? To prove that a new problem $Y$ is NP-Complete:

1. Prove that $Y \in NP$ (a given solution can be verified in polynomial time).
2. Choose a known NP-Complete problem $X$.
3. Prove that $X \le_p Y$ (reduce $X$ to $Y$ in polynomial time). Because $X$ is NP-Complete, all problems in NP reduce to $X$. If $X$ reduces to $Y$, by transitivity, all problems in NP reduce to $Y$, making $Y$ NP-Hard. Since $Y \in NP$ and $Y$ is NP-Hard, $Y$ is NP-Complete.

---

Trace: Reducing 3-SAT to Vertex Cover

To reduce a 3-SAT formula $\phi$ to a Vertex Cover graph $G$:

1. Variables: For each variable $x_i$, create two connected vertices: $x_i$ and $\neg x_i$. (This forces the vertex cover to pick exactly one truth value).
2. Clauses: For each clause (e.g., $x_1 \lor \neg x_2 \lor x_3$), create a triangle of 3 connected vertices. (This forces the vertex cover to pick at least two of these vertices).
3. Connections: Connect the vertices in the clause triangles to their corresponding variable vertices in the variable gadgets.
4. Conclusion: $\phi$ is satisfiable if and only if $G$ has a vertex cover of size $V + 2C$ (where $V$ is the number of variables and $C$ is the number of clauses). Since building this graph takes polynomial time, 3-SAT $\le_p$ Vertex Cover.

High-Yield Subjective Bank: Structure Your Answers

---

####Define P, NP, NP-Complete, and NP-Hard. What is the relation between them? (7 Marks)**

Answer structure:

1. P Class (Polynomial Time) (1.5M):

   • The set of decision problems that can be solved by a deterministic Turing machine in polynomial time $O(n^k)$.
   • These are considered "tractable" or easy problems.
   • Examples: Sorting, Shortest Path, MST.

2. NP Class (Non-deterministic Polynomial Time) (1.5M):

   • The set of decision problems whose proposed solutions can be verified by a deterministic Turing machine in polynomial time.
   • Alternatively, problems that can be solved by a non-deterministic Turing machine in polynomial time.
   • Note: P is a subset of NP.

3. NP-Hard Class (1.5M):

   • A problem $X$ is NP-Hard if every problem $Y \in NP$ can be reduced to $X$ in polynomial time ($Y \le_p X$).
   • These are at least as hard as the hardest problems in NP. They do not have to be in NP themselves (e.g., they might not be decision problems).
   • Example: Halting Problem, TSP Optimization.

4. NP-Complete Class (NPC) (1.5M):

   • A problem is NP-Complete if it satisfies two conditions:
     1. It is in NP.
     2. It is NP-Hard.
   • These are the hardest problems inside NP. If any NP-Complete problem is solved in polynomial time, then $P = NP$.
   • Examples: 3-SAT, Vertex Cover, Graph Coloring.

5. Relationship (Euler Diagram) (1M):

   • Draw the standard diagram showing the relationship assuming $P \neq NP$:
     • A large circle for NP.
     • Inside NP, a smaller circle for P at the bottom.
     • Another circle for NP-Complete at the top of NP, intersecting the boundary.
     • A region outside NP extending upwards representing NP-Hard, where the intersection of NP and NP-Hard forms the NP-Complete region.