—

Artificial Computational Intelligence

Matrix Chain Multiplication and Complexity Classes

Published: 2026-08-09

Level: postgraduate

Audience: Postgraduate students in Artificial Computational Intelligence

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Dynamic programming and the 0/1 knapsack problem — the table-filling recipe and the pseudo-polynomial O(nW) bound — covered in Lecture 11 (Minimum Spanning Trees and Dynamic Programming)
Minimum spanning trees and spanning-tree properties — used in the MST-of-weight-k membership example — covered in Lecture 11
Merge sort and quicksort — the sorting story in the NP discussion — covered in Lecture 9 (Divide and Conquer)
Tower of Hanoi — a running example of an exponential-time problem — covered in Lecture 3 (Analyzing Recursive Algorithms)
Time complexity and asymptotic notation — the language used to define P and NP — covered in Lecture 1 (Data Structures and Algorithm Design)
The fractional knapsack problem — the greedy cousin of the 0/1 knapsack revisited in the complexity discussion — covered in Lecture 8 (Greedy Method)

Two large ideas fill this session, and they are the last two topics of the course. The first is matrix chain product: a dynamic programming problem about choosing the cheapest order in which to multiply several matrices. The second is complexity classes: the P and NP classification that organizes everything we know about fast algorithms, slow algorithms, and the problems whose speed nobody has been able to fix. Both carry exam weight — one heavily, one lightly — and both close a course that began with algorithms, moved through analysis, sorting, graphs, and design strategies, and now asks the biggest question of all: which problems are simply hard to solve?

The two halves connect more tightly than they look. The matrix chain product is one more showcase of dynamic programming, the design strategy from the previous session — it starts with an exponential search and ends with a cubic algorithm, the exact kind of rescue that the second half of the session formalizes. The complexity classes then take that idea and generalize it: some problems have polynomial time algorithms, some seem stuck at exponential time forever, and the theory of P and NP tells us how to think about both. The session's plan is one hour for the algorithm and one hour for the theory, and the theory hour ends with the most famous open question in computer science.

12.1 Where We Left Off: Dynamic Programming

12.1.1 The Recap

The session opened with a recap, because nobody in the room could agree where the previous class had stopped. The answer was 0/1 knapsack — the last dynamic programming example of the previous session. In that problem, we have a set of objects, each with a weight and a value, and a knapsack of capacity $W$ . For each object we must decide whether to take it (1) or leave it (0) — the "0/1" in the name — and the goal is the maximum total value that fits inside the knapsack.

The problem has overlapping subproblems: the same sub-answer (for instance, "best value using the first $i$ objects with remaining capacity $c$ ") is needed again and again inside different branches of a naive recursive solution. The naive recursion recomputes those sub-answers many times, and that is exactly the waste that dynamic programming removes by storing each sub-answer once in a table.

Hook for this session: you already know the trick that turns an exponential problem into a polynomial one — store each sub-answer once instead of recomputing it. Today's question is whether the same trick can find the cheapest way to multiply a chain of matrices, and the answer is a very satisfying yes: an exponential search becomes a table-filling routine.

The two time complexities of 0/1 knapsack. Brute force enumerates every subset of the $n$ objects and runs in $O (2^{n})$ time — there are $2^{n}$ subsets. The dynamic programming version fills an $n$ by $W$ table and runs in $O (nW)$ time, where $n$ is the number of objects and $W$ is the knapsack capacity.

Pseudo-polynomial time. The $O (nW)$ version is called a pseudo-polynomial time algorithm, because its time depends on the numeric value of $W$ rather than only on the size of the input. If $W$ is stored as a number with $b$ bits, then $W$ itself can be as large as $2^{b}$ — so a bound like $nW$ is polynomial in the value of the numbers, not in the number of digits used to write them. That label comes back at the end of this session, when the class compares polynomial time and exponential time and the pseudo-polynomial label of knapsack becomes an examinable subtlety.

The other reminder was the Fibonacci rabbit problem, the first dynamic programming example of the course. Rabbits multiply following Fibonacci numbers, and the naive recursion recomputes the same values again and again; storing them in a table turns the exponential recomputation into linear work. The general properties of dynamic programming — overlapping subproblems, optimal substructure, and solving the smallest subproblems first — were reviewed on the opening slide, purely as reminders of what was already covered.

Recap + bridge: 0/1 knapsack taught the whole recipe — spot overlapping subproblems, define a table of best answers, fill the smallest cells first, reuse everything. Today's algorithm, matrix chain product, uses the identical recipe on a different problem: instead of choosing objects, it chooses where to place parentheses in a matrix product.

12.1.2 Today's Plan

The plan for the session was one dynamic programming algorithm in the first hour — matrix chain product — and the complexity classes in the second hour. The complexity classes topic is the final item of the syllabus, and it counts for a small number of marks, but the recorded lecture videos are part of the course, so this material matters.

Exam note: the recap itself is not the exam target, but its label is: expect the term pseudo-polynomial to be understood, and expect $O (2^{n})$ versus $O (nW)$ for knapsack to be recognized when the session's complexity-class discussion asks which algorithms are in P and which are not.

12.2 Matrix Multiplication Basics

12.2.1 The School Algorithm

Matrix multiplication is the foundation of the whole session, so the class went back to the school algorithm with a small example. Take

$A = (142536)$

$A$ is a 2 by 3 matrix — 2 rows, 3 columns. What order must $B$ have so that $A \cdot B$ makes sense? The compatibility rule is that the number of columns of the first matrix must equal the number of rows of the second matrix. $A$ has 3 columns, so $B$ must have 3 rows. Choose

$B = 791181012$

which is 3 by 2, and the product $C = A \cdot B$ is a 2 by 2 matrix. The dimensions that "cancel" give the order of the answer: 2 by 3 times 3 by 2 leaves 2 by 2.

To compute each entry, multiply the row of $A$ by the column of $B$ , term by term, and add. For example, entry $c_{11}$ comes from row 1 of $A$ and column 1 of $B$ :

$c_{11} = 1 \times 7 + 2 \times 9 + 3 \times 11 = 7 + 18 + 33 = 58$

The same pattern fills the rest of $C$ :

$c_{12} = 1 \times 8 + 2 \times 10 + 3 \times 12 = 8 + 20 + 36 = 64$ $c_{21} = 4 \times 7 + 5 \times 9 + 6 \times 11 = 28 + 45 + 66 = 139$ $c_{22} = 4 \times 8 + 5 \times 10 + 6 \times 12 = 32 + 50 + 72 = 154$

so that

$C = (5813964154)$

Hook: nobody is worried about whether we can multiply matrices — the school algorithm does that. The surprising fact is that the number of single-number multiplications needed is fixed before we start, and it can be read straight off the matrix orders. That count, not the answer, is what the rest of the session is about.

Worked example — the full school-algorithm product. Multiply $A_{2 \times 3}$ by $B_{3 \times 2}$ step by step.

Step 1 — check compatibility: $A$ has 3 columns and $B$ has 3 rows, so the product exists. The result is 2 by 2: the outer dimensions 2 and 2 survive, the shared 3 cancels.

Step 2 — entry $c_{11}$ (row 1 of $A$ , column 1 of $B$ ): $1 \times 7 + 2 \times 9 + 3 \times 11 = 58$ .

Step 3 — entry $c_{12}$ (row 1 of $A$ , column 2 of $B$ ): $1 \times 8 + 2 \times 10 + 3 \times 12 = 64$ .

Step 4 — entry $c_{21}$ (row 2 of $A$ , column 1 of $B$ ): $4 \times 7 + 5 \times 9 + 6 \times 11 = 139$ .

Step 5 — entry $c_{22}$ (row 2 of $A$ , column 2 of $B$ ): $4 \times 8 + 5 \times 10 + 6 \times 12 = 154$ .

Final answer: $C = (5813964154)$ , and the product $A \cdot B$ is a valid 2 by 2 matrix.

Sense-check: every entry is a dot product of a 3-number row with a 3-number column, so each entry mixes exactly three products; the corner entries match the arithmetic done above, and the shapes cancel correctly (2 by 3 × 3 by 2 → 2 by 2).

12.2.2 Counting Scalar Multiplications

Each entry of $C$ is one dot product with 3 multiplications in it, and there are 4 entries, so the total number of primitive (single number) multiplications is 12. The neat way to see this: multiply the three dimensions that appear in the orders — rows of the first matrix (2), the shared middle dimension (3), and columns of the second matrix (2):

$multiplications = 2 \times 3 \times 2 = 12$

In general, multiplying a $p$ by $q$ matrix with a $q$ by $r$ matrix costs $p \times q \times r$ scalar multiplications and produces a $p$ by $r$ matrix. The middle dimension $q$ appears in the orders of both matrices but in neither order of the result — it "cancels". This single fact drives the whole matrix chain product problem, so it is worth stating as a rule:

$cost (A_{p \times q} \cdot B_{q \times r}) = p \cdot q \cdot r, result order p \times r$

The cost rule (the tool of this session): multiplying $A_{p \times q}$ with $B_{q \times r}$ needs exactly $p \cdot q \cdot r$ scalar multiplications, and the result is a $p \times r$ matrix. The three numbers are the rows of the first matrix, the shared middle dimension, and the columns of the second matrix. Given only the orders of two matrices, the multiplication count is known before any arithmetic runs.

Why the middle dimension cancels: the result entry $c_{ij}$ is the sum $\sum_{k = 1}^{q} a_{ik} b_{k j}$ , and the index $k$ runs over the $q$ shared columns/rows. That is why $q$ shows up once as a factor in the count but disappears from the result's shape — it is summed away, not carried through.

Visual intuition: picture the two matrices as rectangles of sizes $p \times q$ and $q \times r$ standing side by side. The two inner edges — the $q$ side of both — touch, and the product rectangle is formed by the two outer edges, $p \times r$ . The cost is the volume of the three dimensions $p$ , $q$ , $r$ , and the result's area is only $p \times r$ . The cancelled middle dimension is the joint the two rectangles share.

Scope: the rule assumes the standard school algorithm for multiplying two matrices — every entry is a full dot product. Faster algorithms exist (for example, Strassen's divide-and-conquer method), but the cost counting in this session always uses the school algorithm, and that is also the convention the exam follows.

Pitfalls:

Trying to multiply matrices whose inner dimensions differ — a $p \times q$ times an $r \times s$ product with $q \neq = r$ simply does not exist.
Writing the result shape as $p \times q$ or $q \times r$ : the result is always the outer pair, $p \times r$ .
Forgetting the middle dimension in the count: the cost is $p \times q \times r$ , all three numbers, not just $p \times r$ .

12.2.3 Student Questions and Answers

Q: What order must $B$ have so that $A$ , a 2 by 3 matrix, can be multiplied with it? A: $B$ must be 3 by 2 (or any matrix with 3 rows and any number of columns). The number of columns in the first matrix must equal the number of rows in the second matrix, so the 3 columns of $A$ force 3 rows of $B$ .

Q: How many scalar multiplications are needed for this $A$ times $B$ ? A: Twelve. Count 2 times 3 times 2: the rows of the first matrix, the shared middle dimension, and the columns of the second matrix. Given only the orders of the input matrices, you can read off the multiplication count without doing any arithmetic.

12.2.4 Exam Notes

Exam note: the cost formula $p \times q \times r$ for a $p$ by $q$ times $q$ by $r$ product is the single tool used again and again in the matrix chain product problem, which is a known exam item. Expect to compute these counts by hand, quickly and without a calculator.

12.3 The Matrix Chain Product Problem

12.3.1 Associativity and the Catch

Matrix multiplication is associative: $(B \cdot C) \cdot D$ gives exactly the same matrix as $B \cdot (C \cdot D)$ , so we may parenthesize a product any way we wish, and the final answer is unchanged. A parenthesization is just a choice of where the brackets go — for three matrices, either $((A_{1} \cdot A_{2}) \cdot A_{3})$ or $(A_{1} \cdot (A_{2} \cdot A_{3}))$ . That is the freedom.

The catch is that the number of primitive multiplications used to reach that answer is not the same for every parenthesization. Multiply the same three matrices in two different orders and you can do noticeably different amounts of arithmetic — while computing the same result. Matrix multiplication is not commutative, so the matrices keep their order; only the grouping of the multiplications is free. Associativity gives the freedom of grouping; commutativity would have given a freedom we do not have.

Hook: two different bracketings of the same three matrices can differ in cost by more than a factor of two — and the gap only widens as the chain grows. Which bracketing is cheapest is not a detail; for long chains it is the difference between seconds and hours of computing.

Intuition: think of joining wooden boards into a long plank. No matter how you group the joins, the final plank is the same — that is associativity. But the cost of each join depends on the sizes of the pieces being joined, so grouping the joins differently changes the total work, and a smart order does the big pieces first while they are still small.

12.3.2 Problem Statement

The matrix chain product problem is: given a collection of $n$ two-dimensional matrices $A_{1}, A_{2}, \dots, A_{n}$ whose product we want, decide how to parenthesize the product so that the total number of scalar multiplications is minimized. Note the careful wording: the problem is not to perform the multiplication and find the matrix answer; it is only to decide the order in which the multiplication is performed. The answer matrix is the same in every parenthesization, so the value is never in question — only the cost of computing it. And as the number of matrices grows, the difference between a good and a bad parenthesization grows large, so the choice really matters.

Definition (matrix chain product problem): given a chain $A_{1} \cdot A_{2} \dots A_{n}$ of $n$ matrices, find a parenthesization that minimizes the total number of scalar multiplications. The product itself is identical for every parenthesization; only the computational cost changes.

Why the problem makes sense: because the final matrix is fixed, the value of the problem is entirely in the cost. Determining the cheapest order is worth its own effort when $n$ is large, because the time spent choosing a good order is repaid by the time saved in the actual multiplications.

12.3.3 Worked Example: Two Parenthesizations of B, C, D

Here is the small demonstration that starts the topic. Suppose $B$ is 3 by 100, $C$ is 100 by 5, and $D$ is 5 by 5. First parenthesize as $(B \cdot C) \cdot D$ .

Worked example — $(B \cdot C) \cdot D$ versus $B \cdot (C \cdot D)$ with $B$ 3×100, $C$ 100×5, $D$ 5×5.

Parenthesization 1 — $(B \cdot C) \cdot D$ :

Step 1 — compute $B \cdot C$ . Cost: $3 \times 100 \times 5 = 1500$ scalar multiplications. The result is a 3 by 5 matrix (the 100 cancels).

Step 2 — multiply that 3 by 5 result with the 5 by 5 matrix $D$ . Cost: $3 \times 5 \times 5 = 75$ .

Total: $1500 + 75 = 1575$ scalar multiplications.

Parenthesization 2 — $B \cdot (C \cdot D)$ :

Step 1 — compute $C \cdot D$ . Cost: $100 \times 5 \times 5 = 2500$ . The result is a 100 by 5 matrix.

Step 2 — multiply the 3 by 100 matrix $B$ with that result. Cost: $3 \times 100 \times 5 = 1500$ .

Total: $2500 + 1500 = 4000$ scalar multiplications.

Final answer: $(B \cdot C) \cdot D$ costs 1575 multiplications and $B \cdot (C \cdot D)$ costs 4000 — the same final matrix, but the first order does less than half the arithmetic.

Sense-check: in the cheap order the intermediate matrix stays small (3 by 5), so the expensive final join is only $3 \times 5 \times 5 = 75$ ; in the expensive order the intermediate $C \cdot D$ grows to 100 by 5, and every later multiplication pays for that size.

Pitfalls:

Thinking the cheaper parenthesization is the one that starts with the most expensive-looking pair. The opposite trick is at work: the best order usually creates small intermediate matrices, so the expensive joins never get the chance to happen at full size.
Believing the problem asks for the matrix answer. It asks only for the order; the answer matrix is the same everywhere.
Dropping or reordering matrices: matrix multiplication is associative but not commutative, so $A_{2} A_{1}$ is not an option when the chain is $A_{1} A_{2}$ .

12.3.4 Student Questions and Answers

Q: Can $A_{1} \cdot A_{2} \cdot A_{3} \cdot A_{4}$ be written as $(A_{1} \cdot A_{2} \cdot A_{3}) \cdot (A_{3} \cdot A_{4})$ ? A: No. That split repeats $A_{3}$ — it appears in both pieces, and the two pieces of a split must not overlap. Splitting the chain $A_{1} \dots A_{4}$ after position 2 gives $(A_{1} \cdot A_{2}) \cdot (A_{3} \cdot A_{4})$ ; splitting after position 3 gives $(A_{1} \cdot A_{2} \cdot A_{3}) \cdot A_{4}$ , where the second piece is the single matrix $A_{4}$ . Every valid split of a chain has the form $A [i .. k]$ followed by $A [k + 1.. j]$ .

Recap + bridge: associativity makes every parenthesization legal, and the cost rule from the previous section makes every parenthesization measurable. The problem is now well defined — minimize the total over all bracketings — and the next question is how many bracketings there are to check. That count decides whether brute force is even an option.

12.4 Why Brute Force Fails: Catalan Numbers

12.4.1 Counting Parenthesizations

How many different ways are there to parenthesize a chain of $n$ matrices? The answer is a known number sequence: the Catalan numbers. For a product of $n$ matrices there are $C_{n - 1}$ parenthesizations, where

$C_{n - 1} = \frac{1}{n} (n - 1 2 n - 2)$

This is the standard closed form of the Catalan number $C_{n - 1}$ : the binomial coefficient $(n - 1 2 n - 2)$ (the number of ways to choose $n - 1$ positions out of $2 n - 2$ ), divided by $n$ . The session named the sequence but did not state the closed form; the standard definition of a Catalan number is $C_{m} = \frac{1}{m + 1} (m 2 m)$ , and substituting $m = n - 1$ gives exactly the form above.

Counting parenthesizations. The count of fully parenthesized products of $n$ matrices follows the recurrence

$P (1) = 1, P (n) = k = 1 \sum n - 1 P (k) P (n - k) for n \geq 2$

The reasoning: a fully parenthesized product splits between the $k$ -th and $(k + 1)$ -st matrices for some $k$ from 1 to $n - 1$ , and each side is itself a fully parenthesized product. The solution of this recurrence is the Catalan numbers, with $P (n) = C_{n - 1}$ .

Small values. For $n = 3$ : $C_{2} = \frac{1}{3} (2 4) = \frac{6}{3} = 2$ — matching the two parenthesizations of $B, C, D$ worked above. For $n = 4$ : $C_{3} = \frac{1}{4} (3 6) = \frac{20}{4} = 5$ . For $n = 5$ : $C_{4} = \frac{1}{5} (4 8) = \frac{70}{5} = 14$ .

Scope: the count $C_{n - 1}$ assumes every matrix order is fixed and only the grouping changes — this is a count of binary parenthesizations, not of matrix permutations. The number of full binary trees with $n$ leaves is the same sequence, which is why the same numbers appear in many other counting problems.

12.4.2 The Growth Rate

The growth is roughly 4 to the power $n$ — the session put it as "almost 4 power $n$ ". The precise asymptotic behaviour is $C_{n - 1} \in Θ (4^{n} / n^{3/2})$ : the count grows like $4^{n}$ divided by a small polynomial factor. Enumerating every parenthesization and picking the best is a terrible algorithm: the number of options explodes so quickly that brute force is hopeless even for moderately sized chains. That is exactly why the problem needs dynamic programming. The journey from about $4^{n}$ possibilities down to a polynomial algorithm is the whole point of the solution that follows.

Visual intuition: plot the number of parenthesizations against $n$ , with $n$ on the horizontal axis and the count on the vertical axis. The curve starts gently — 1, 2, 5, 14 — then bends sharply upward like an exponential: by $n = 20$ the count already exceeds ten billion, and by $n = 30$ it is beyond $1 0^{16}$ . The takeaway is that the counting of options outruns any computer long before the chain is long.

Pitfalls:

Confusing the count with $2^{n}$ . The number of parenthesizations is a Catalan number — larger than $2^{n}$ for all but the smallest chains — so brute force over parenthesizations is even worse than brute force over $2^{n}$ choices.
Using the wrong index: a chain of $n$ matrices has $C_{n - 1}$ parenthesizations, not $C_{n}$ . The sequence starts at $C_{1} = 1$ for a single matrix.
Believing the count grows "almost linearly". A power-of-4 growth rate is exponential in the exponent's constant: each added matrix multiplies the option count by about 4.

Recap + bridge: brute force over parenthesizations costs about $4^{n}$ options and is hopeless; the recurrence $P (n) = \sum_{k} P (k) P (n - k)$ shows the options explode with every matrix. Dynamic programming replaces the whole search with a table of subchain costs, and the notation needed to name those subchains comes next.

12.5 Input Representation and Notation

12.5.1 The Dimension Array

The input to the matrix chain product problem is not a list of matrices; it is a list of dimensions. Given an array with $n + 1$ numbers, $D_{0}, D_{1}, \dots, D_{n}$ , we interpret it as $n$ matrices, where the $i$ -th matrix $A_{i}$ has order $D_{i - 1}$ by $D_{i}$ . For example, if the input array is 10, 20, 30, 40, 50, then $A_{1}$ is 10 by 20, $A_{2}$ is 20 by 30, $A_{3}$ is 30 by 40, and $A_{4}$ is 40 by 50 — four matrices from five numbers, because consecutive entries share one dimension. That sharing is what makes the chain multiply at all.

Hook: one array of $n + 1$ numbers silently describes $n$ matrices — because matrix $i$ ends where matrix $i + 1$ begins. The whole problem is solved from this array alone; the actual numbers inside the matrices never enter the computation.

Definition (dimension array): for an array $D_{0}, D_{1}, \dots, D_{n}$ , the $i$ -th matrix of the chain is $A_{i} = D_{i - 1} \times D_{i}$ . Every adjacent pair of matrices shares a dimension — $A_{i}$ 's second dimension is $A_{i + 1}$ 's first — so the chain can be multiplied, and the shared dimensions are exactly the "cancel" dimensions of the cost rule.

Worked reading of an array: input 10, 20, 30, 40, 50 gives $A_{1}$ 10×20, $A_{2}$ 20×30, $A_{3}$ 30×40, $A_{4}$ 40×50. The count is always one less than the array length: five numbers, four matrices.

Pitfalls:

Thinking the input is the matrices themselves. Only the orders are given; the problem never multiplies actual numbers.
Misreading the pairing: $A_{i}$ uses $D_{i - 1}$ and $D_{i}$ , not $D_{i}$ and $D_{i + 1}$ — an off-by-one here breaks every join cost later.
Assuming the array length equals the matrix count: $n + 1$ numbers always mean $n$ matrices.

12.5.2 The A[i..j] Notation

Write $A [i .. j]$ for the product of matrices $A_{i}, A_{i + 1}, \dots, A_{j}$ , multiplied in that order in some as-yet-unknown parenthesization. So $A [1..3]$ means $A_{1} \cdot A_{2} \cdot A_{3}$ and $A [1..2]$ means $A_{1} \cdot A_{2}$ . The boundary case matters most: $A [i .. i]$ is just the single matrix $A_{i}$ , with no multiplication at all, so its cost is zero. Every split of a chain is of the form

$A [i .. j] = A [i .. k] \cdot A [k + 1.. j], i \leq k < j$

and the dynamic programming solution builds every subchain $A [i .. j]$ in this way, reusing the already-computed subchains on both sides.

Definition (subchain notation): $A [i .. j]$ is the product of the contiguous block of matrices $A_{i}$ through $A_{j}$ , in that order. A split of the subchain at position $k$ writes it as $A [i .. k] \cdot A [k + 1.. j]$ with $i \leq k < j$ — the split point is any matrix boundary strictly inside the chain. The boundary $A [i .. i]$ is a single matrix with zero cost, which becomes the base case of the recurrence.

What order does $A [i .. j]$ have? The product of $A_{i}$ (order $D_{i - 1} \times D_{i}$ ) through $A_{j}$ (order $D_{j - 1} \times D_{j}$ ) has order $D_{i - 1} \times D_{j}$ : the first matrix's first dimension and the last matrix's second dimension survive, and everything between cancels. This is why a join of $A [i .. k]$ and $A [k + 1.. j]$ costs $D_{i - 1} \cdot D_{k} \cdot D_{j}$ — the three outer dimensions of the pair.

Visual intuition: think of the chain as a row of $n$ dominoes. $A [i .. j]$ is the product of the block of dominoes from tile $i$ to tile $j$ , and $A [i .. k] \cdot A [k + 1.. j]$ is cutting the block at a seam. The cut must fall strictly inside the block ( $k < j$ ) and cannot miss any tile ( $k \geq i$ ), and the two pieces must never overlap — a cut at the edge of the block leaves one side empty.

12.5.3 Student Questions and Answers

Q: What does $A [1..1]$ mean? Is it $A_{1}$ times $A_{1}$ , the square of $A_{1}$ ? A: No. $A [1..1]$ means only the matrix $A_{1}$ — there is no multiplication at all, so it costs zero scalar multiplications. $A [1..3]$ means $A_{1} \cdot A_{2} \cdot A_{3}$ and $A [1..2]$ means $A_{1} \cdot A_{2}$ ; the notation counts matrices from $i$ through $j$ , so $A [1..1]$ stops before any multiplication happens.

Recap + bridge: the dimension array $D_{0} \dots D_{n}$ encodes the whole problem in $n + 1$ numbers, and $A [i .. j]$ names every subproblem — the product of any contiguous block of matrices. With subproblems named and the split form $A [i .. k] \cdot A [k + 1.. j]$ in hand, the dynamic programming tables can be defined.

12.6 The Dynamic Programming Tables and Recurrence

12.6.1 The M Table

We keep a table $M$ where $M [i, j]$ stores the minimum number of scalar multiplications needed to compute the subchain $A [i .. j]$ . The table is $n$ by $n$ , and because we only ever consider chains with $i \leq j$ , we use the diagonal and everything above it. The smallest subproblems are the single-matrix chains: computing $A [i .. i]$ needs no multiplication at all, so every diagonal entry is

$M [i, i] = 0$

That diagonal is the base case of the recursion. The question the algorithm answers is $M [1, n]$ — the cost of the whole chain.

Definition (the M table): $M [i, j]$ is the minimum number of scalar multiplications needed to compute $A [i .. j]$ . The base case is $M [i, i] = 0$ for every $i$ , because a single matrix costs nothing to "multiply". The table is only filled on and above the diagonal — $i \leq j$ — since a chain from $i$ to $j$ with $i > j$ is meaningless. The final answer is $M [1, n]$ .

12.6.2 The S Table

A second table $S$ stores, for each pair $(i, j)$ , the split position used in the optimal parenthesization of $A [i .. j]$ : the $k$ at which the chain was divided into $A [i .. k]$ and $A [k + 1.. j]$ . The $M$ table alone gives the minimum cost; the $S$ table is what lets us reconstruct the actual parenthesization afterwards. Without $S$ we would know how cheaply the product can be computed, but not how.

Definition (the S table): $S [i, j]$ records the split position $k$ that produced the minimum in the recurrence for $M [i, j]$ . It is written alongside $M$ : every time a new minimum is chosen for $M [i, j]$ , the winning $k$ is stored in $S [i, j]$ . After the tables are full, $S$ is walked from $S [1, n]$ downward to print the optimal parenthesization.

12.6.3 Mathematical Formulation

For a chain $A [i .. j]$ with $i < j$ , the last multiplication joins the left subchain $A [i .. k]$ and the right subchain $A [k + 1.. j]$ for some split $k$ between $i$ and $j$ . The cost of that join depends only on the outer dimensions: the left subchain has order $D_{i - 1}$ by $D_{k}$ and the right has order $D_{k}$ by $D_{j}$ , so the final join costs $D_{i - 1} \cdot D_{k} \cdot D_{j}$ . The total cost of that choice is the left subchain's minimum plus the right subchain's minimum plus the join cost, and we take the best $k$ :

$M [i, j] = i \leq k < j min (M [i, k] + M [k + 1, j] + D_{i - 1} \cdot D_{k} \cdot D_{j})$

The working rule from the session: $k$ is the split position, $D$ is the array of orders, and the last term is computed blindly from the order array as $D_{i - 1}$ into $D_{k}$ into $D_{j}$ . Whenever the minimum comes from a particular $k$ , record that $k$ in $S [i, j]$ .

Why the recurrence is correct (optimal substructure). If the optimal parenthesization of $A [i .. j]$ splits at $k$ , then the two pieces must themselves be optimal: if $A [i .. k]$ could be computed more cheaply, replacing it inside the optimal parenthesization would lower the total, contradicting optimality. So the minimum total is built from the minima of both subchains plus the unavoidable join cost — and trying every possible $k$ guarantees the true optimum is considered. This is the same optimal substructure that the 0/1 knapsack recurrence used.

Why the join cost is $D_{i - 1} \cdot D_{k} \cdot D_{j}$ : the left subchain has order $D_{i - 1} \times D_{k}$ (its first matrix starts at $D_{i - 1}$ , its last ends at $D_{k}$ ), the right subchain has order $D_{k} \times D_{j}$ , and the cost rule says multiplying them costs the product of the three outer dimensions. Only the two outermost dimensions of the whole chain and the split dimension appear — the interior dimensions have all cancelled inside the subchains.

Symbols named: $i, j$ are chain endpoints ( $1 \leq i \leq j \leq n$ ), $k$ is the split position running from $i$ to $j - 1$ , $D_{i - 1}, D_{k}, D_{j}$ are entries of the dimension array, and $M [i, k]$ , $M [k + 1, j]$ are the already-computed minima of the two subchains.

12.6.4 The Build Order

We fill the table bottom-up, from smallest chains to largest. First all chains of length 1 (the diagonal, cost 0). Then all chains of length 2: for each pair of neighbours there is only one possible split, and the formula reduces to $D_{i - 1} \cdot D_{i} \cdot D_{j}$ . Then chains of length 3, then 4, and so on, until the whole chain $A [1.. n]$ is computed. Each longer chain uses only values that are already in the table, because every subchain it needs is shorter. This is the classic dynamic programming structure: smallest subproblem first, build up, reuse.

Intuition: filling the table is like building a pyramid from the base. Every cell $M [i, j]$ is supported by two cells beneath it — $M [i, k]$ on its left and $M [k + 1, j]$ below-left — which are strictly shorter chains, so already computed. The order of work is fixed by chain length, not by any guess about which multiplication looks cheapest.

Scope: the recurrence assumes every subchain has one well-defined minimum cost — which holds because multiplication costs depend only on dimensions, never on the numbers inside the matrices. If the chain contained incompatible matrices (adjacent dimensions that do not match), the input itself would be invalid and the recurrence would be meaningless; the dimension-array representation guarantees compatibility by construction.

Pitfalls:

Starting with a pair of matrices that looks cheap instead of starting with the length-1 diagonal. The base case is always $M [i, i] = 0$ ; nothing else may be filled first.
Forgetting to update $S$ when $M$ changes. The split position must be recorded at the same moment the minimum is recorded, or the parenthesization cannot be reconstructed later.
Trying to compute $M [i, j]$ from longer chains: a cell may only use cells with shorter chain length, which is exactly what the length-by-length build order guarantees.

Recap + bridge: the recurrence $M [i, j] = min_{k} (M [i, k] + M [k + 1, j] + D_{i - 1} D_{k} D_{j})$ with base case $M [i, i] = 0$ defines the whole algorithm, and the $S$ table records how each minimum was reached. The next step is to run this machinery on real numbers and watch the tables fill.

12.7 Worked Example: Dimensions 5, 4, 6, 2, 7

12.7.1 Setting Up the Tables

Run the algorithm on four matrices whose order array is 5, 4, 6, 2, 7. Reading off the orders: $A_{1}$ is 5 by 4, $A_{2}$ is 4 by 6, $A_{3}$ is 6 by 2, and $A_{4}$ is 2 by 7. The target is $M [1, 4]$ — the minimum number of scalar multiplications for the whole chain. Draw two 4 by 4 tables: $M$ for costs and $S$ for split positions. Fill the diagonal of $M$ with zeros (single matrices cost nothing) and leave the diagonal of $S$ empty.

12.7.2 Chains of Length Two

The smallest real subproblems pair neighbouring matrices.

$M [1, 2]$ — the cost of $A_{1} \cdot A_{2}$ : $5 \times 4 \times 6 = 120$ . With two matrices there is nothing to parenthesize: the only split is after $A_{1}$ , so $S [1, 2] = 1$ .

$M [2, 3]$ — the cost of $A_{2} \cdot A_{3}$ : $4 \times 6 \times 2 = 48$ , and $S [2, 3] = 2$ .

$M [3, 4]$ — the cost of $A_{3} \cdot A_{4}$ : $6 \times 2 \times 7 = 84$ , and $S [3, 4] = 3$ .

The $M$ table now has its first upper diagonal: 120, 48, 84.

12.7.3 Chains of Length Three

Now the real decisions begin, because a chain of three matrices has two possible parenthesizations.

$M [1, 3]$ — the chain $A_{1} \cdot A_{2} \cdot A_{3}$ , split either after $A_{1}$ or after $A_{2}$ .

Split $k = 1$ : left is $A_{1}$ alone ( $M [1, 1] = 0$ ), right is $A_{2} \cdot A_{3}$ ( $M [2, 3] = 48$ ), and the join multiplies the 5 by 4 matrix $A_{1}$ with the 4 by 2 result of $A_{2} \cdot A_{3}$ , costing $5 \times 4 \times 2 = 40$ . Total: $0 + 48 + 40 = 88$ .

Split $k = 2$ : left is $A_{1} \cdot A_{2}$ ( $M [1, 2] = 120$ ), right is $A_{3}$ alone ( $M [3, 3] = 0$ ), and the join multiplies the 5 by 6 result of $A_{1} \cdot A_{2}$ with the 6 by 2 matrix $A_{3}$ , costing $5 \times 6 \times 2 = 60$ . Total: $120 + 0 + 60 = 180$ .

Take the minimum: $M [1, 3] = 88$ , and because the minimum came from $k = 1$ , $S [1, 3] = 1$ . The winner is $A_{1} \cdot (A_{2} \cdot A_{3})$ .

$M [2, 4]$ — the chain $A_{2} \cdot A_{3} \cdot A_{4}$ , split either after $A_{2}$ or after $A_{3}$ .

Split $k = 2$ : $M [2, 2] + M [3, 4]$ plus the cost of joining $A_{2}$ with the result of $A_{3} \cdot A_{4}$ . The result of $A_{3} \cdot A_{4}$ is 6 by 7, so the join is $4 \times 6 \times 7 = 168$ . Total: $0 + 84 + 168 = 252$ .

Split $k = 3$ : $M [2, 3] + M [4, 4]$ plus the cost of joining the result of $A_{2} \cdot A_{3}$ with $A_{4}$ . The result of $A_{2} \cdot A_{3}$ is 4 by 2, so the join is $4 \times 2 \times 7 = 56$ . Total: $48 + 0 + 56 = 104$ .

Minimum: $M [2, 4] = 104$ , and because the minimum came from $k = 3$ , $S [2, 4] = 3$ . The winner is $(A_{2} \cdot A_{3}) \cdot A_{4}$ .

Note the discipline: after computing a candidate value we do not write it into the table immediately — we wait until all splits are evaluated, then write the minimum. And whenever $M$ is updated, $S$ must be updated too.

12.7.4 The Final Chain M[1,4]

The last cell is the answer. The chain $A_{1} \cdot A_{2} \cdot A_{3} \cdot A_{4}$ has three possible splits: after $A_{1}$ , after $A_{2}$ , or after $A_{3}$ .

Split $k = 1$ — $(A_{1}) \cdot (A_{2} \cdot A_{3} \cdot A_{4})$ : $M [1, 1] + M [2, 4]$ plus the join cost. The result of $A_{2} \cdot A_{3} \cdot A_{4}$ has order 4 by 7 (the 6 and the 2 cancel), so the join with the 5 by 4 matrix $A_{1}$ costs $5 \times 4 \times 7 = 140$ . Total: $0 + 104 + 140 = 244$ .

Split $k = 2$ — $(A_{1} \cdot A_{2}) \cdot (A_{3} \cdot A_{4})$ : $M [1, 2] + M [3, 4]$ plus the join cost. The result of $A_{1} \cdot A_{2}$ has order 5 by 6 and the result of $A_{3} \cdot A_{4}$ has order 6 by 7, so the join costs $5 \times 6 \times 7 = 210$ . Total: $120 + 84 + 210 = 414$ .

Split $k = 3$ — $(A_{1} \cdot A_{2} \cdot A_{3}) \cdot (A_{4})$ : $M [1, 3] + M [4, 4]$ plus the join cost. The result of $A_{1} \cdot A_{2} \cdot A_{3}$ has order 5 by 2, so the join with the 2 by 7 matrix $A_{4}$ costs $5 \times 2 \times 7 = 70$ . Total: $88 + 0 + 70 = 158$ .

The minimum of 244, 414, and 158 is 158, so $M [1, 4] = 158$ and $S [1, 4] = 3$ . The final answer: the chain product $A_{1} \cdot A_{2} \cdot A_{3} \cdot A_{4}$ can be computed with 158 scalar multiplications.

Worked example — the full run on dimensions 5, 4, 6, 2, 7.

Step 1 — read the orders from the dimension array: $A_{1}$ 5×4, $A_{2}$ 4×6, $A_{3}$ 6×2, $A_{4}$ 2×7.

Step 2 — base case: fill the diagonal of $M$ with $M [i, i] = 0$ .

Step 3 — chains of length two: $M [1, 2] = 5 \times 4 \times 6 = 120$ (S = 1); $M [2, 3] = 4 \times 6 \times 2 = 48$ (S = 2); $M [3, 4] = 6 \times 2 \times 7 = 84$ (S = 3).

Step 4 — chains of length three. For $M [1, 3]$ : $k = 1$ gives $0 + 48 + 5 \times 4 \times 2 = 88$ , $k = 2$ gives $120 + 0 + 5 \times 6 \times 2 = 180$ , so $M [1, 3] = 88$ with $S [1, 3] = 1$ . For $M [2, 4]$ : $k = 2$ gives $0 + 84 + 4 \times 6 \times 7 = 252$ , $k = 3$ gives $48 + 0 + 4 \times 2 \times 7 = 104$ , so $M [2, 4] = 104$ with $S [2, 4] = 3$ .

Step 5 — the whole chain $M [1, 4]$ : $k = 1$ gives $0 + 104 + 5 \times 4 \times 7 = 244$ , $k = 2$ gives $120 + 84 + 5 \times 6 \times 7 = 414$ , $k = 3$ gives $88 + 0 + 5 \times 2 \times 7 = 158$ .

Final answer: $M [1, 4] = 158$ , $S [1, 4] = 3$ , and the parenthesization $(A_{1} \cdot (A_{2} \cdot A_{3})) \cdot A_{4}$ — the same 158 that the multiplication sequence in the next section confirms.

Sense-check: every subchain cost is built only from shorter subchains, every join cost uses the three outer dimensions of the pair, and the winning split at each level is the one that keeps intermediate matrices small — the 5 by 2 result at the end is what makes $k = 3$ cheap.

The completed tables look like this. $M$ (minimum costs), with rows indexed by $i$ and columns by $j$ :

M[i,j]	1	2	3	4
1	0	120	88	158
2		0	48	104
3			0	84
4				0

$S$ (split positions):

S[i,j]	2	3	4
1	1	1	3
2		2	3
3			3
4

Exam note: a common exam version of this problem gives four matrices and asks you to deduce $M [1, 4]$ — exactly what we did here — and the same question can come with five or six matrices, where the same table-filling procedure runs one or two steps further. Write the full $M$ and $S$ tables; the split positions in $S$ are part of the expected answer because they are what the next section uses to rebuild the parenthesization.

12.7.5 Student Questions and Answers

Q: What is the smallest subproblem here? Some students suggested $A_{2}$ into $A_{3}$ . A: The smallest subproblem is a single matrix — $A_{1}$ alone, or $A_{2}$ alone, and so on — with zero multiplications. Do not pick the subproblem by guessing which multiplication looks cheapest; the algorithm's first step is always the smallest subproblem in size, which is one matrix. $A_{2} \cdot A_{3}$ is a chain of length two, which comes in a later step.

Q: How many scalar multiplications does $M [1, 2]$ need? A: 120. $A_{1}$ is 5 by 4 and $A_{2}$ is 4 by 6, so the count is $5 \times 4 \times 6 = 120$ .

Q: What is the order of the result of $A_{2} \cdot A_{3}$ ? A: 4 by 2. The shared dimension 6 cancels: 4 by 6 times 6 by 2 leaves 4 by 2. That order is exactly what the join cost $5 \times 4 \times 2$ in the first $M [1, 3]$ split is built on.

Q: Several students said the split position $S [1, 3]$ should be 2. Why is the answer 1? A: The answer is 1 because the minimum 88 came from the first split, $k = 1$ , which groups $A_{1}$ alone with $(A_{2} \cdot A_{3})$ . The split position records where the winning parenthesization splits, not a value we choose for convenience.

Q: In the $M [2, 4]$ calculation, what is the join cost for the split after $A_{2}$ ? A: 168. The result of $A_{3} \cdot A_{4}$ is 6 by 7, so joining $A_{2}$ (4 by 6) with it costs $4 \times 6 \times 7 = 168$ , giving $0 + 84 + 168 = 252$ — the losing candidate.

Q: And for the split after $A_{3}$ ? A: 56. The result of $A_{2} \cdot A_{3}$ is 4 by 2, so joining with $A_{4}$ (2 by 7) costs $4 \times 2 \times 7 = 56$ , giving $48 + 0 + 56 = 104$ — the winner, which is why $S [2, 4] = 3$ .

Q: For $M [1, 4]$ , where do the three join costs 140, 210, and 70 come from? A: From the outer dimensions of each split. $k = 1$ joins $A_{1}$ (5 by 4) with the 4 by 7 result of the rest: $5 \times 4 \times 7 = 140$ . $k = 2$ joins the 5 by 6 result of $A_{1} \cdot A_{2}$ with the 6 by 7 result of $A_{3} \cdot A_{4}$ : $5 \times 6 \times 7 = 210$ . $k = 3$ joins the 5 by 2 result of $A_{1} \cdot A_{2} \cdot A_{3}$ with $A_{4}$ : $5 \times 2 \times 7 = 70$ .

Q: Why are there only three possibilities for $A_{1} \dots A_{4}$ ? What about an option like $(A_{1} \cdot A_{2} \cdot A_{3}) \cdot A_{4}$ written differently? A: That option is the third possibility, $k = 3$ — it is already included. Any parenthesization of four matrices splits the chain exactly once into two non-empty pieces, and the split can fall after matrix 1, 2, or 3, and nowhere else. Enumerating "many different possibilities" by eye counts the same parenthesizations multiple times; the three splits are exhaustive.

Recap + bridge: the tables are full: $M$ holds every minimum cost and $S$ holds every winning split. The answer $M [1, 4] = 158$ is verified by the split bookkeeping, and the next step reads the parenthesization back from $S$ .

12.8 Reading the Parenthesization Back

12.8.1 Reconstructing the Order

The $S$ table now gives the full parenthesization. Start at $S [1, 4] = 3$ : the whole chain splits after matrix 3, so the product is $(A_{1} \cdot A_{2} \cdot A_{3}) \cdot A_{4}$ . Now resolve the left piece: $S [1, 3] = 1$ , so $A_{1} \cdot A_{2} \cdot A_{3}$ splits after matrix 1, giving $A_{1} \cdot (A_{2} \cdot A_{3})$ . The inner piece $A_{2} \cdot A_{3}$ has $S [2, 3] = 2$ , a two-matrix chain with nothing to rearrange. The final parenthesization comes out as

$(A_{1} \cdot (A_{2} \cdot A_{3})) \cdot A_{4}$

How to walk the S table. The reconstruction is a small recursion driven by $S$ . Start at $(i, j) = (1, n)$ . If $i = j$ , the block is a single matrix and the walk stops. Otherwise read $k = S [i, j]$ , split the block as $A [i .. k]$ and $A [k + 1.. j]$ , and recurse on both pieces. The result is a fully parenthesized expression. In the example: $S [1, 4] = 3$ splits into $A [1..3]$ and $A [4..4]$ ; $S [1, 3] = 1$ splits into $A [1..1]$ and $A [2..3]$ ; $S [2, 3] = 2$ is a two-matrix block, done. Concatenating the pieces with parentheses gives $(A_{1} \cdot (A_{2} \cdot A_{3})) \cdot A_{4}$ .

Why the S table is needed at all: the $M$ table answers "how cheap?" but not "how?". Two different parenthesizations can produce the same minimum cost only if their costs tie, and in general the cheapest grouping is not visible from the cost numbers alone. The split positions recorded during the minimization are the only record of which grouping won, which is why updating $S$ whenever $M$ is updated is a rule, not a courtesy.

Pitfalls:

Reading $S [1, n]$ and stopping: the walk must continue recursively into both pieces until every block is a single matrix.
Mixing up which side of the split comes first: the split always reads $A [i .. k]$ then $A [k + 1.. j]$ , left subchain before right.
Reconstructing from $M$ instead of $S$ : cost values cannot tell you which $k$ won; only $S$ can.

12.8.2 The Multiplication Sequence

The parenthesization says how the work actually runs. First compute $A_{2} \cdot A_{3}$ , costing 48. Then multiply $A_{1}$ with that result, costing $5 \times 4 \times 2 = 40$ . Finally multiply that with $A_{4}$ , costing $5 \times 2 \times 7 = 70$ . Total: $48 + 40 + 70 = 158$ — the same number the table promised. Nothing about the two-matrix product $A_{2} \cdot A_{3}$ cares whether $A_{1}$ or $A_{4}$ joins later; the grouped product is taken together and then combined, and the arithmetic order of the two later steps does not change the count.

Worked example — the multiplication sequence for the optimal order.

Step 1 — compute $A_{2} \cdot A_{3}$ : the pair costs $4 \times 6 \times 2 = 48$ and produces a 4 by 2 matrix.

Step 2 — multiply $A_{1}$ (5 by 4) by that 4 by 2 result: cost $5 \times 4 \times 2 = 40$ , producing a 5 by 2 matrix.

Step 3 — multiply the 5 by 2 result by $A_{4}$ (2 by 7): cost $5 \times 2 \times 7 = 70$ , producing the final 5 by 7 product.

Final answer: total cost $48 + 40 + 70 = 158$ , matching $M [1, 4]$ exactly.

Sense-check: the three costs are precisely the subchain minima and join costs that the recurrence chose — $M [2, 3] = 48$ , the $k = 1$ join for $M [1, 3]$ (40), and the $k = 3$ join for $M [1, 4]$ (70) — so the table's promise and the step-by-step execution agree.

Recap + bridge: the $S$ table turns a number, $M [1, 4] = 158$ , into an executable plan, $(A_{1} \cdot (A_{2} \cdot A_{3})) \cdot A_{4}$ , whose step-by-step cost matches the table. With correctness checked on real numbers, the remaining question is how fast the whole table can be filled — the time complexity of the algorithm.

12.9 Time Complexity of Matrix Chain Product

12.9.1 Three Nested Loops

The algorithm has three nested loops, each running to about $n$ : the loop over chain length, the loop over start positions $i$ , and the loop over split positions $k$ . Each loop runs to the order of $n$ , so the total time is

$O (n^{3})$

with $n$ the number of matrices. The class-level shortcut — "there are three for loops, so it is $n$ cube" — works here, with one caveat worth internalizing: three loops alone do not guarantee $n$ cube; the loops must each run to the order of $n$ , which is exactly the case in this algorithm.

Why the time is O(n³). The work is dominated by the innermost statement — evaluating the sum $M [i, k] + M [k + 1, j] + D_{i - 1} D_{k} D_{j}$ and comparing it with the current minimum. The chain-length loop runs for lengths $L = 2, \dots, n$ ; for a fixed length $L$ there are $n - L + 1$ start positions $i$ ; and for a fixed $(i, j)$ pair there are $L - 1$ split positions $k$ . The total number of inner evaluations is

$L = 2 \sum n (n - L + 1) (L - 1) = \frac{n ^{3} - n}{6} = O (n^{3})$

So the cubic bound is exact, not just a guess: about one sixth of $n^{3}$ candidate splits in total. The space is $O (n^{2})$ — the two $n$ by $n$ tables $M$ and $S$ .

The shortcut and its caveat: three nested loops that each run to $O (n)$ do give $O (n^{3})$ — but the reason is the loop bounds, not the count three. Two loops of length $n$ and one of length $n^{2}$ would also be three loops with a different total; here every bound is order $n$ , and the bound is what the big-O cares about.

Pitfalls:

Quoting $O (n^{3})$ without the caveat: the bound is right, but the justification must be that each of the three loops runs to the order of $n$ .
Confusing the space with the time: the tables are $n \times n$ , so the space is $O (n^{2})$ , while the filling time is $O (n^{3})$ .
Forgetting the table cost in the sum: each of the $O (n^{3})$ evaluations reads two table cells and writes one, which is constant work per evaluation.

12.9.2 Student Questions and Answers

Q: What is the time complexity of the matrix chain product algorithm? A: Big O of $n$ cube. The chain-length loop, the start-position loop, and the split-position loop all run to the order of $n$ . The standard set for the class: if the time complexity cannot be read off this algorithm at a glance, the teaching has failed.

Hook for the comparison: brute force parenthesization search grows like about $4^{n}$ , while this table-filling algorithm needs $O (n^{3})$ — for 30 matrices, $4^{30}$ is beyond $1 0^{18}$ options, while $3 0^{3} = 27, 000$ table cells' worth of work is instant. That gap is the entire point of the dynamic programming approach.

Recap + bridge: three nested loops of order $n$ give $O (n^{3})$ time and $O (n^{2})$ space, replacing a $Θ (4^{n} / n^{3/2})$ brute-force search — the exponential-to-polynomial rescue that the complexity-classes half of the session will frame in general terms. Before the theory half, a quick tour of where the problem shows up in practice.

12.10 Applications of Matrix Chain Product

12.10.1 Data Science and Machine Learning

Matrix multiplication is everywhere in modern data science — principal component analysis (PCA) and support vector machines (SVM), both central to machine learning and data mining, multiply matrices at every step, and the cost of those multiplications follows the same counting rules as this problem. Anyone who studied the mathematical foundations of data science (MFDS) will recognize the linear algebra immediately.

Real-world connection: in a typical machine learning pipeline, one computation after another is a matrix product — covariance matrices in PCA, kernel matrices in SVM, weight matrices in a neural network's forward pass. Each product's cost is governed by the same rule $cost = p \cdot q \cdot r$ , and whenever a product of several matrices is needed, the cheapest bracketing is found by exactly the algorithm of this session. Modern deep learning frameworks apply these orderings automatically when they compile a computation graph.

12.10.2 NLP

Natural language processing (NLP) has its own applications of matrix chain product — the course notes list several that belong to the NLP and machine learning courses, and the standing takeaway is that the technique has extensive application in today's data science work, not just in theory.

12.10.3 Circuits and Networks

Even before data science, matrix chain product ideas appear in network analysis and circuit analysis. In electrical circuits, ABCD matrices are used to compute the voltage along a chain of circuit components; multiplying those transmission matrices in a good order is precisely a chain product. The details sit outside the course's domain, but the connection is a useful anchor for remembering that the problem is not an academic toy.

Recap + bridge: the same cost rule powers PCA, SVM, NLP pipelines, and circuit analysis — wherever several matrices are multiplied, the cheap bracketing pays. This closes the dynamic programming half of the session; the second hour steps back and asks the general question: which problems admit polynomial time algorithms at all, and which seem condemned to exponential time?

12.11 Why Study Complexity Classes?

12.11.1 The Research Motivation

The last topic of the course is complexity classes: P, NP, NP hard, NP complete. The first question is why we study them at all, and the honest answer is that P and NP are research areas. The scope of that research is to take algorithms whose time is exponential and find polynomial time algorithms for them. Every algorithm we studied earlier in the course — sorting, searching, shortest paths — has a polynomial time solution, but many important problems do not. The fastest known sorting algorithms all need about $n lo g n$ time; research asks whether something faster exists. For a linear time algorithm we would love a constant time algorithm; for a quadratic time algorithm we would love a polynomial one; and for every exponential time algorithm the dream is a polynomial one. Nobody has yet succeeded in converting the hard exponential time problems into polynomial time, and until that happens, the work already done on them must not be lost. That preservation is what the classification system does: the work done in trying to move exponential problems toward polynomial ones is organized and preserved under the names P, NP, NP complete, and NP hard.

The research program in one sentence: take every exponential-time problem and try to find a polynomial-time algorithm for it. The classes P, NP, NP hard, and NP complete are the filing system that keeps this program organized — they record which problems have been solved, which have not, and how the unsolved ones are connected to each other.

Why the previous topics all belong to P: sorting ( $O (n lo g n)$ ), searching ( $O (n)$ or $O (lo g n)$ ), and shortest paths are all problems whose best-known algorithms run in polynomial time. They sit on the "solved" side of the research program; the exponential problems on the other side are the ones the classification exists for.

12.11.2 The Shared-Blame Analogy

The organizing idea is easy to grasp with an everyday analogy. When a student cannot do an assignment and a friend also has not done it, the natural move is to share the blame: if my friend also did not do it, then I am not alone. Complexity classes work the same way. Unable to find a linear time algorithm for, say, the traveling salesperson problem (TSP), we look for another problem of the same difficult nature — Tower of Hanoi, for example — and tie the two together: if somebody someday solves Tower of Hanoi, then our problem will be solved too. We find associations between problems that are all exponential or NP time, so that if any one of them falls, they all fall. When we cannot solve a problem, we relate it to a problem that is already known to be hard, and that association is the beginning of the whole theory of reductions.

The shared-blame analogy (from the session): you could not do the assignment, and your friend could not do it either. Sharing the blame makes you feel less alone — the failure is not yours alone, it is a group condition. The research version: we cannot find a polynomial algorithm for TSP, and nobody can find one for Tower of Hanoi either, so we group the two together. If someday someone cracks one of them, the association carries the solution to the other. That is the emotional and logical core of the theory: connection as shared fate.

Where the analogy breaks: blame-sharing is about feelings and does not change whether the assignment gets done; reductions are precise mathematical statements — a solution to one problem really does produce a solution to the other, in polynomial time. The analogy captures the motive, not the mechanism.

Pitfalls:

The common failure named in the session: believing in advance that the topic cannot be understood. The mental block is the main obstacle — the topic itself is not complex, and the definitions are short.
Thinking P and NP are about "fast" and "slow" in an everyday sense. They are about asymptotic worst-case time: polynomial versus exponential growth of running time with input size.
Believing the classification is finished. It is an active research area; the boundary between the solved and unsolved problems is exactly what the classes exist to study.

Recap + bridge: complexity classes exist to preserve the work of an open research program — finding polynomial time algorithms for exponential problems — and the shared-blame analogy shows how one hard problem's fate is tied to another's. The next step is to define the two problem types that the classes are built around: decision problems and optimization problems.

12.12 Decision Problems and Optimization Problems

12.12.1 Two Kinds of Problems

The complexity classes are built around two kinds of problems. A decision problem is one whose intended output is yes or no. An optimization problem is one where we try to maximize or minimize something. The two are closely related, and the connection between them is the tool we use again and again.

Definition (decision problem): a computational problem whose intended output is a single bit — yes or no. Example: "given a graph and an integer $k$ , does the graph have a spanning tree of weight at most $k$ ?" The output is either "yes" or "no", nothing more.

Definition (optimization problem): a computational problem whose output is the best value of something — the maximum profit, the minimum cost, the shortest path. Example: "given a weighted graph, find a minimum weight spanning tree."

Why decision problems come first: the classes P and NP are defined for problems with a yes/no answer, because "yes" or "no" is something an algorithm can certify and verify cleanly. Optimization problems are then connected to decision problems by the parameter trick below — and a hard decision version makes its optimization version hard too.

12.12.2 Turning Optimization into Decision

Introduce a parameter $k$ and ask whether the optimal value is at most $k$ or at least $k$ . That one trick converts any optimization problem into a decision problem. If we can decide "is the optimum at most 10 hours?", we can search over $k$ to find the optimum itself, so solving all the decision versions is essentially as powerful as solving the optimization version.

Intuition: asking "what is the best possible?" is a search over an infinite range of answers; asking "is the best possible at least this good?" is a single yes/no question. A binary search over $k$ converts many yes/no answers into the exact optimum — decide "is it at most $k$ ?" repeatedly, narrowing the gap each time, and the optimum is pinned down. The two problem forms are two sides of the same coin, which is why the theory studies the decision forms while practitioners usually care about the optimization forms.

12.12.3 Worked Examples: TSP and Knapsack

Worked example — the traveling salesperson problem (TSP).

A Hamiltonian cycle in a graph is a cycle that passes through every vertex exactly once.

Optimization version: given a weighted graph, find a Hamiltonian cycle of minimum weight.

Decision version: given a weighted graph and an integer $k$ , is there a Hamiltonian cycle with total weight at most $k$ ?

The concrete picture: a salesperson starts at one place, visits all the others, and returns to the start, spending minimum time or cost. "Can this trip be completed within 10 hours?" is the decision version, with 10 hours playing the role of $k$ . If the answer is yes, try $k = 9$ hours; if yes again, try 8 — and so on until the smallest yes gives the minimum trip time. Each yes/no answer is a single decision instance, and the sequence of decisions locates the optimum.

Sense-check: a minimum-weight Hamiltonian cycle is exactly a Hamiltonian cycle whose weight is at most $k$ for every $k$ down to its own weight — the decision answers "yes" for all larger $k$ and "no" below, and the boundary value is the optimum.

Worked example — the knapsack problem.

Optimization version: find the subset of objects that maximizes profit (while fitting the capacity).

Decision version: is there a subset of objects that fits the knapsack and has a total value of at least $k$ ?

Same objects, same capacity — the yes-or-no question replaces the maximization. To recover the maximum value itself, ask the decision question with increasing $k$ : the largest $k$ that still answers yes is the maximum achievable value.

Sense-check: if the optimum value is $V^{*}$ , the decision version answers yes for every $k \leq V^{*}$ and no for every $k > V^{*}$ ; scanning $k$ from small to large finds $V^{*}$ at the transition point.

Pitfalls:

Forgetting the direction of the inequality: minimization problems ("at most $k$ ") flip to "at least $k$ " when the optimization problem is a maximization.
Thinking the decision version is easier to solve. The trick converts the problem form, not its difficulty: if the optimization version is hard, its decision version is hard in exactly the same way.
Assuming the search over $k$ must be linear. It can be a binary search, but the theory only needs the equivalence: decision answers for all $k$ determine the optimum.

Recap + bridge: decision problems ask yes or no; optimization problems maximize or minimize; and the parameter $k$ converts each into the other. Every problem named in the classes below — P, NP, and beyond — is studied in its decision form, and with both forms defined, the first class, P, can be defined precisely.

12.13 Class P: Polynomial Time

12.13.1 Definition

Class P consists of all problems that are solvable in polynomial time. A problem is solvable in polynomial time when an algorithm for it runs in time $n$ to the power $k$ for some constant $k$ , where $n$ is the size of the input to the problem:

$T (n) = O (n^{k}), k a constant$

The key point is the definition of $n$ : the size of the input. Polynomial growth means the time grows polynomially as the input size grows — linear, quadratic, cubic, and so on — the shape every algorithm we studied in the asymptotic notation sessions has. Search takes $O (n)$ , sorting takes $O (n lo g n)$ : both polynomial. The exponential algorithms on the other side — like brute force 0/1 knapsack at $O (2^{n})$ — are not in P by this definition.

Definition (class P): the set of all decision problems for which an algorithm exists that runs in time $O (n^{k})$ for some constant $k$ , where $n$ is the size of the input. $O (n lo g n)$ counts as polynomial too — it is bounded above by $O (n^{2})$ , so sorting is in P — while $O (2^{n})$ , $O (3^{n})$ , and $O (n!)$ are not.

Why the constant $k$ is allowed to be anything: the definition only demands that the exponent is fixed and independent of the input. An $O (n^{10})$ algorithm is technically polynomial, even if it is slow in practice; the class is a mathematical boundary, not a speed rating.

Named symbols: $T (n)$ is the worst-case running time as a function of input size, $n$ is the size of the input (the number of bits or basic items needed to write it down), and $k$ is the constant exponent of the polynomial.

Scope: the definition of P measures the running time against the size of the input. For a problem whose input is a number $W$ , the input size is the number of digits needed to write $W$ , not the value $W$ itself — which is why a bound like $O (nW)$ can escape P: $W$ can be exponentially larger than the number of digits. This subtlety is what makes the 0/1 knapsack bound pseudo-polynomial, as reviewed at the start of the session.

Exam note: the definition of P, with the size of the input as $n$ , is a classic short conceptual question. Be ready to state it exactly: solvable in $O (n^{k})$ time for a constant $k$ , with $n$ the input size.

12.13.2 Why Polynomial Time Matters

Polynomial time is the boundary worth caring about because it is predictable. With pen and paper, during the design phase, we can analyze an algorithm and know its polynomial time complexity before ever running it on a machine — we can state in advance that a solution will arrive within a known bound. Exponential time gives no such promise, which is why the whole research program of the field is aimed at pulling exponential problems down into polynomial ones.

Why polynomial is the boundary: two properties separate it from every slower growth rate. First, polynomial time is predictable in design — a polynomial bound can be established on paper, before any machine runs, so the algorithm's budget is known in advance. Second, polynomial growth stays tractable as inputs grow: doubling the input multiplies the work by a constant factor $2^{k}$ , while exponential growth squares the work with every added input item. The session's framing is direct: time is the resource we cannot waste, and polynomial time gives a promise exponential time cannot.

Pitfalls:

Writing $n^{k}$ with $n$ as the number of operations: $n$ is the input size, and $k$ is a constant — a running time of $O (n^{n})$ or $O (n^{n /2})$ is not polynomial because the exponent depends on $n$ .
Counting $O (2^{n})$ as "almost polynomial": doubling the input squares the time, and the class definition rejects it outright.
Forgetting that $O (n lo g n)$ is polynomial: any $lo g n$ factor is dominated by a polynomial, so $n lo g n = O (n^{2})$ .

Recap + bridge: P is the set of problems solvable in $O (n^{k})$ time for a constant $k$ , and its practical meaning is predictability — the polynomial bound is known before the machine runs. The next question is what happens when no polynomial algorithm is known: that is where non-deterministic algorithms enter.

12.14 Deterministic and Non-deterministic Algorithms

12.14.1 Deterministic Algorithms

A deterministic algorithm gives a fixed output for a given input: give the same input twice and the same output comes out both times. Every algorithm from earlier in the course is deterministic. Feed an array to merge sort and we know exactly what happens: it sorts in $n lo g n$ time, and the result is the same every run. Feed a search problem — search for element $x$ in an array $a_{1} \dots a_{n}$ — and a deterministic linear search checks positions one by one and either returns the index $j$ where $a_{j}$ equals $x$ , or returns 0 when $x$ is absent. The behaviour is known in advance: the output is one of the positions or a failure signal, and the time is order $n$ .

Definition (deterministic algorithm): an algorithm whose every step is fixed by the input and the previous steps; running it twice on the same input produces the same output both times. Merge sort, linear search, and every algorithm in the earlier sessions are deterministic — the computation path is fully determined from the start.

12.14.2 The Choice Function

Now suppose we imagine that the search problem has never been solved — we travel back to an era before linear search and binary search existed. What can we write then? A strange algorithm: let $j = choice (a, n)$ ; if $a_{j}$ equals $x$ , return $j$ ; otherwise return 0. The function choice is the unknown part. We do not know what choice does, how long it takes, or which value $j$ it returns — that is the non-deterministic part of the algorithm. But the important observation is the checking step: given the value $j$ that choice produces, checking whether $a_{j}$ contains $x$ is quick — polynomial time. So the algorithm has one non-deterministic piece (guessing $j$ ) and one polynomial piece (verifying the guess). Later, when smarter people found real algorithms for search, the choice function got its explanation: linear search, binary search, or similar replaced it. The non-deterministic gap was filled in.

Worked example — search written with a choice function.

The problem: given an array $a_{1}, \dots, a_{n}$ and a value $x$ , return an index $j$ with $a_{j} = x$ , or 0 if $x$ is absent.

The non-deterministic algorithm:

Step 1 — guess: $j = choice (a, n)$ . The choice function hands back some index $j$ between 1 and $n$ , with no specification of how it chose it.

Step 2 — verify: check whether $a_{j} = x$ . This comparison takes constant time; scanning the array to confirm absence takes $O (n)$ time at worst. Either way, the verification is polynomial.

Step 3 — output: return $j$ if the check passed, otherwise 0.

Final answer: the guess supplies the candidate, the check supplies the correctness, and the algorithm has the two-phase shape — non-deterministic guess plus polynomial verification.

Sense-check: if the array actually contains $x$ at position 3 and choice returns 3, the algorithm outputs the right answer; if choice returns a wrong position, the check rejects it and the algorithm reports failure — the verification is what keeps the guess honest.

12.14.3 Two-Phase Structure of Non-deterministic Algorithms

This two-part shape is the definitional core of the whole topic. A non-deterministic algorithm has two phases. In the first phase, a procedure makes a guess about the possible solution to the problem. In the second phase, another procedure — call it the verifier — checks whether the guessed solution really is a solution, and this checking phase can be done in polynomial time. The guessing phase is the magic box; the verification phase is the honest work. Whenever we cannot write a polynomial time algorithm, we can still write the guessing part and say: later, when somebody finds an explanation for choice, our problem will be solved.

Definition (non-deterministic algorithm): an algorithm with two phases — (1) a guessing phase in which a choice function produces a candidate solution with no prescribed method, and (2) a verification phase in which the candidate is checked in polynomial time. If a problem admits such an algorithm, it belongs to the class defined in the next section. The choice function is a stand-in: whenever a real polynomial algorithm is later discovered, the choice function can be replaced by it.

Why this is useful: the guess is free — it can magically pick the right candidate — so the hard work is only in the verification. A problem whose solutions are easy to check is "easy to solve" in the non-deterministic sense, even when nobody knows a deterministic polynomial algorithm for it.

12.14.4 Student Questions and Answers

Q: Can you give a real example of a non-deterministic algorithm from everyday computing? A: Think of concurrent execution. During the execution of multiple threads in parallel, we may not be able to predict exactly what happens — even for the same input, the interleaving can differ from run to run. That unpredictability — more than one path being taken — is the flavour of non-determinism. It is an analogy, not the formal definition, but it builds the right intuition.

Q: What happens if choice is given input like 0, 0? A: Do not get stuck on concrete values for the guess. We are standing in a hypothetical era where search has never been solved, and $a$ and $n$ are the inputs of the actual problem; the point is the structure: choice hands back a candidate position, and we verify it. The details of which value is passed in are beside the idea.

Q: Why do we need to write the non-deterministic algorithm now, before anybody has explained how choice works? If the explanation is found later, can we not just write the polynomial algorithm then? A: Because your work in the meantime must not be lost. Suppose you spend seven years on a PhD trying to find a linear time algorithm for Tower of Hanoi and do not fully succeed. All that work would vanish without a framework to keep it. The P and NP classification is that framework: it preserves the work and the relationships between unsolved problems. That is the practical reason the theory exists. The same thing happened historically with sorting — when nobody knew how to sort, a non-deterministic sorting algorithm was written, with a choice function that hands back positions for the numbers; later, when merge sort and quicksort appeared, the choice got its explanation.

Pitfalls:

Treating the guess as a real implementation: choice is a stand-in for a future algorithm, not a subroutine anyone can call today.
Forgetting the verification phase: a guess alone proves nothing; the polynomial-time check is what makes the algorithm meaningful.
Reading "non-deterministic" as "random". Randomness is a specific probability distribution; non-determinism here is an unspecified but guaranteed-to-exist correct guess — a much stronger assumption than luck.

Recap + bridge: deterministic algorithms give one fixed output per input; non-deterministic algorithms guess a candidate and verify it in polynomial time. The guessing phase is the magic box, the verification is the honest work — and the class NP is precisely the set of problems solvable by such two-phase algorithms.

12.15 Class NP: Non-deterministic Polynomial Time

12.15.1 Definition

Class NP consists of all problems that can be solved in polynomial time by non-deterministic algorithms. Given the two-phase structure just described, that means: a non-deterministic guessing procedure, followed by a verification procedure that runs in polynomial time. If a problem admits such an algorithm, it belongs to NP. The "N" is the sticking point for almost every student, and the name is worth repeating several times until it sticks: non-deterministic polynomial — not non-polynomial, and never anything else.

Definition (class NP): the set of all decision problems that can be solved by a non-deterministic algorithm — a guessing phase that produces a candidate answer, followed by a verifier that checks the candidate in polynomial time. Equivalently, a problem is in NP when a proposed solution can be verified in polynomial time.

Why "verifiable" and "solvable by a non-deterministic algorithm" are the same thing: if a verifier can check a candidate in polynomial time, then a non-deterministic algorithm solves the problem by having the choice function guess the candidate and running the verifier on it. The two definitions are two sides of one coin: NP is the class of problems whose solutions are easy to check, even when finding them is hard.

Hook: the same problem can be brutally hard to find the answer to, yet very easy to check an answer for. NP is the formal name for exactly that situation — and almost every problem you will ever meet in practice belongs to it.

12.15.2 The Name Correction

Q: Is NP short for non-polynomial time? A: No. NP is not non-polynomial; it means non-deterministic polynomial time. The advice given to the class: say "non-deterministic polynomial" at least five times in your mind and make it firm, because the whole course's grasp of the definition rests on that name. A non-deterministic polynomial time algorithm is one with a guess plus a polynomial-time check.

Pitfalls:

Expanding NP as "non-polynomial". That reading is wrong twice over: the "N" stands for non-deterministic, and NP problems are verifiable in polynomial time.
Thinking NP means "hard". There are NP problems that are easy (everything in P is also in NP), so NP is not a hardness label — the hardness labels come in a later section.
Forgetting the verifier: a problem is in NP because a guess plus a polynomial-time check solves it, not because the problem "looks" hard.

12.15.3 The Sorting Story

The clearest way to see what NP means historically is the sorting story. At one time nobody knew how to sort numbers at all. A non-deterministic sorting algorithm was written: the choice function is asked for a value $j$ for each position — for the first number, this is the location; for the second number, this is the location; for the third number, this is the location — and if the choice function hands back that order, the algorithm checks whether the order is correct. Verifying a given order is easy in polynomial time: walk through it and check that it is sorted. The guessing part is non-deterministic. Later, when merge sort, quicksort, and heap sort came into existence, people found the explanation for choice: the non-deterministic guess was replaced by real sorting logic. Sorting moved from the NP column to the P column. Other problems have not been so lucky — they still wait in NP for their choice functions to be explained.

Worked example — sorting as a non-deterministic algorithm.

The problem: sort the array $a_{1}, \dots, a_{n}$ into non-decreasing order.

Step 1 — guess the order: choice hands back a permutation — for the first number a location $j_{1}$ , for the second a location $j_{2}$ , and so on. If the guess is a valid permutation, the numbers are placed accordingly.

Step 2 — verify: walk through the placed numbers and check that each is no larger than the next. This is a single pass, $O (n)$ time — polynomial.

Step 3 — accept the guess if the check passes, reject it otherwise.

Final answer: non-deterministic sorting is a correct algorithm — the choice function guarantees the right permutation exists, and the check rejects everything else. The explanation of choice arrived historically as merge sort, quicksort, and heap sort, and sorting joined P.

Sense-check: a wrong guess (out-of-order arrangement) is caught by the walk; the correct permutation is always guessed by choice; so the non-deterministic algorithm always reaches a sorted array — the same guarantee a real sorting algorithm provides.

Recap + bridge: NP is the class of problems solvable by a guess plus a polynomial-time check, and the sorting story shows a problem moving from NP to P when its choice function is explained. Every problem in P is automatically in NP — which sets up the famous question: is P equal to NP?

12.16 P ⊆ NP and the P = NP Question

12.16.1 Asking the Question Two Ways

With both classes defined, the obvious question follows: is P equal to NP? Ask it in two directions. Can we write an NP algorithm for every P algorithm? Yes — easy. Any deterministic polynomial time algorithm can be turned into a non-deterministic one by replacing its logic with a choice function; the verification is the original algorithm itself. The reverse direction: can we write a P time algorithm for every NP time algorithm? That is the question nobody can answer. So the status is one-sided: P is a subset of NP, and whether the two sets are the same is unknown — the most famous open question in computer science, listed among the Millennium Prize problems. If somebody proves that any single NP problem is in P, the whole research area collapses into a yes: all of NP would be in P, because every NP problem is connected to every other by the reductions described next.

The one-sided relationship. Every deterministic polynomial time algorithm is automatically a non-deterministic one: throw away the algorithm's logic, let choice guess the answer, and verify by running the original algorithm. So every problem in P is in NP, written

$P \subseteq N P$

The reverse inclusion — is every NP problem in P? — is the unanswered direction, and it is the question the whole field waits on.

What a proof would do: because every NP problem reduces to every other, proving that any single NP problem has a polynomial time algorithm would drag all of NP into P in one stroke, making P = NP. That single-problem trigger is why the question is asked about whole classes: one solution solves everything.

Hook: the Clay Mathematics Institute lists the P versus NP question among the seven Millennium Prize problems, each carrying a million-dollar prize. The question can be stated to a stranger in one sentence — can every problem whose answers are easy to check also have its answers easy to find? — yet nobody has answered it in more than fifty years.

Visual intuition: draw two circles, one labelled P inside a larger one labelled NP. Every problem with a known polynomial algorithm sits in the inner circle; every problem with a guess-and-check algorithm sits in the outer one. The open question is whether the outer circle has anything at all outside the inner one — nobody has ever exhibited a problem provably inside NP and outside P, and nobody has proved none exists.

12.16.2 Student Questions and Answers

Q: Why do we emphasize polynomial time so much? Why is polynomial the boundary? A: Because time is the resource we cannot waste — we do not want to wait a day or a minute for a result, we want it as early as possible. And polynomial time has a second advantage: with pen and paper, during design, we can already predict the time complexity of a polynomial time algorithm and know it will finish within a bounded time, without going near a machine. Exponential time gives neither promise.

Q: Several students asked whether solving all NP problems with P algorithms would end the research. A: That is exactly why the question is interesting. P is a subset of NP — many problems that once sat in NP have been pulled into P as technology improved, but plenty remain outside it. The research goal is precisely to find polynomial time solutions for those remaining problems, one at a time, and bring them inside the P circle.

Pitfalls:

Believing P = NP is "probably false, so ignore it". The question shapes the entire field: approximation algorithms, heuristics, and cryptography all rest on the working assumption that the classes differ — but the assumption is unproven.
Thinking a problem "being in NP" means it is hard or unsolved. Every P problem is in NP too, so NP membership alone carries no difficulty information.
Forgetting that only the decision forms matter: the P = NP question is about decision problems; optimization versions are connected to them through the parameter trick from the earlier section.

Recap + bridge: $P \subseteq N P$ is proven; $P = N P$ is the famous open question, and any single NP problem pulled into P would collapse the classes. The next step is the toolkit that answers membership questions one problem at a time: how to prove that a given problem belongs to NP.

12.17 Proving a Problem is in NP

12.17.1 Two Routes to NP Membership

How do we prove that a given problem belongs to NP? The easiest route: show the problem is in P. If a deterministic polynomial time algorithm exists, replace its logic by a choice function and we immediately get a non-deterministic algorithm — so every P problem is automatically in NP. The other route, when we do not know a polynomial algorithm: write a non-deterministic algorithm directly — a choice function that guesses the solution, plus a polynomial time verifier. If the verifier exists, the problem is in NP.

The two membership proofs. Route 1 — P implies NP: a deterministic polynomial time algorithm is a non-deterministic algorithm with an explained choice function; its verifier is the algorithm itself. Route 2 — guess and verify: specify what the choice function guesses (a candidate certificate) and show that checking it runs in polynomial time. The certificate is the formal name for the guessed object — the solution witness that the verifier inspects.

What a verifier must be: an algorithm that takes the problem instance and a certificate, runs in polynomial time, and answers yes exactly when the certificate is a genuine solution. The certificate's size must also be polynomial in the input size — a verifier is not allowed to receive a giant witness.

12.17.2 Worked Example: MST of Weight K

Apply this to a concrete decision problem: decide whether a given graph has a minimum spanning tree (MST) of weight exactly $k$ . A spanning tree on $n$ vertices has exactly $n - 1$ edges — we studied this: a tree on $n$ vertices must connect all of them, and the last vertex connects with the $n - 1$ -st edge. So the choice function can be written to output $n - 1$ edges. If the choice function hands us those $n - 1$ edges, we can easily check whether they form a spanning tree and whether its total weight is $k$ . The check runs in $O (n + m)$ time, where $n$ is the number of vertices and $m$ is the number of edges — polynomial. Guessing part non-deterministic, checking part polynomial: the decision problem "does this graph have an MST of weight $k$ ?" is in NP.

Why the certificate is $n - 1$ edges: a spanning tree on $n$ vertices always uses exactly $n - 1$ edges — enough to connect all vertices with no cycles. The guess has a fixed, known shape, and the verifier tests three things about it: it has $n - 1$ edges, it connects all vertices (no disconnected pieces), and its total weight equals $k$ .

Worked example — proving "MST of weight k" is in NP.

The problem: given a graph with $n$ vertices and $m$ edges, decide whether it has a spanning tree of total weight exactly $k$ .

Step 1 — guess the certificate: the choice function outputs $n - 1$ edges of the graph.

Step 2 — verify connectivity and tree-ness: check that the chosen edges touch all $n$ vertices and contain no cycle. This can be done with a single traversal (for example, a union-find pass over the edges, or a depth-first scan from any vertex counting edges and visited vertices), costing $O (n + m)$ time.

Step 3 — verify the weight: sum the weights of the $n - 1$ edges and compare with $k$ . One pass over $n - 1$ numbers, $O (n)$ time.

Final answer: the guess supplies $n - 1$ edges, and the check runs in $O (n + m)$ time — polynomial — so the decision problem is in NP.

Sense-check: every genuine spanning tree of weight $k$ is a certificate the guess may produce and the verifier accepts, and every accepted certificate is genuinely a spanning tree of weight $k$ — the verifier accepts nothing else, which is exactly what membership requires.

Pitfalls:

Guessing the whole tree "somehow" without stating the certificate: the guess must be a well-defined object (here, $n - 1$ edges) so the verifier has something concrete to check.
Forgetting that the verifier must reject bad certificates, not just accept good ones — the check "does it connect everything and weigh $k$ " does both.
Claiming membership with a non-polynomial verifier: the verification phase must be polynomial, or the problem has not been shown to be in NP by this route.

Recap + bridge: membership in NP is proved by finding a certificate and a polynomial-time verifier — the MST example certifies $n - 1$ edges and checks them in $O (n + m)$ . The same guess-and-verify pattern now moves to the problem at the centre of the whole theory: satisfiability.

12.18 The Satisfiability Problem

12.18.1 What SAT Asks

The satisfiability problem (SAT) is the first known NP problem, and it is easy to state. A Boolean formula is satisfiable if there exists some assignment of the values 0 and 1 to its variables that causes the whole formula to evaluate to 1. The question SAT asks: given a Boolean formula, is it satisfiable? The answer to find is a truth assignment — for example, in a four-variable formula, the assignment $x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1$ might be the one that satisfies it. A human can spot such an assignment for small formulas, but a machine must search for it.

Definition (satisfiability): a Boolean formula in the variables $x_{1}, \dots, x_{n}$ is satisfiable when at least one assignment of 0 or 1 to the variables makes the whole formula evaluate to 1. The SAT problem asks, for a given formula, whether such an assignment exists — a decision problem with a yes/no answer.

What a satisfying assignment is: a complete truth table row — every variable gets exactly one value, and the formula's value under that row is 1. The assignment $x_{1} = 0, x_{2} = 0, x_{3} = 1, x_{4} = 1$ is one such row for a four-variable formula.

12.18.2 CNF Satisfiability

The standard shape for SAT formulas is conjunctive normal form (CNF): an AND of $r$ clauses. Inside the brackets, each clause is a disjunction (OR) of literals — variables or their negations — and all $r$ clauses are ANDed together; for the whole formula to be 1, every clause must be 1. The session described CNF as an AND of $r$ clauses; the clause-as-OR-of-literals detail is the standard definition, and together they say: the formula is 1 exactly when every one of the $r$ clauses is 1. The problem: find an assignment of 0 or 1 to the variables such that the whole CNF formula evaluates to 1.

Definition (CNF): a formula in conjunctive normal form is

$(C_{1} \land C_{2} \land \dots \land C_{r})$

an AND of $r$ clauses, where each clause $C_{j}$ is an OR of literals:

$C_{j} = (l_{j 1} \lor l_{j 2} \lor \dots \lor l_{j s})$

and each literal $l$ is a variable $x_{i}$ or its negation $\neg x_{i}$ . The whole formula evaluates to 1 exactly when every clause evaluates to 1 — a single 0 inside one clause makes that clause 0, and one 0 clause makes the whole AND 0.

Named symbols: $r$ is the number of clauses, $s$ is the number of literals in a clause, $\land$ means AND, $\lor$ means OR, and $\neg x_{i}$ is the negation of variable $x_{i}$ . A literal is a single variable or its negation; a clause is an OR of literals; the formula is an AND of clauses.

Pitfalls:

Thinking the formula is satisfied when some clause is 1: the clauses are ANDed, so every clause must be 1.
Confusing AND and OR: the outer connectors are ANDs between clauses, the inner connectors are ORs inside each clause.
Forgetting negations: a literal may be $\neg x_{i}$ , and a formula can be satisfiable only by assignments where negated literals are 0 when the variable is 1.

12.18.3 The Brute Force Cost

How long does brute force take? With $n$ variables, every assignment is a different combination of 0s and 1s, and there are

$2^{n}$

possible assignments — exponential time. A formula with three variables has 8 assignments to try (000, 001, 010, 011, 100, 101, 110, 111); the count doubles with every added variable. An exponential time algorithm is not something we can live with, so the question is whether SAT can be done in polynomial time — and that question is exactly why SAT sits at the centre of the P = NP debate.

Worked example — the brute force count.

A formula on $n$ variables has one assignment per row of a truth table: variable 1 gets 0 or 1, variable 2 gets 0 or 1, and so on. By the multiplication rule, $2 \times 2 \times \dots \times 2 = 2^{n}$ rows.

For $n = 3$ : the assignments are 000, 001, 010, 011, 100, 101, 110, 111 — exactly $2^{3} = 8$ , each row to be evaluated against the formula.

For $n = 30$ : $2^{30} \approx 1.07$ billion assignments. For $n = 60$ : $2^{60}$ exceeds a billion billion.

Final answer: brute force SAT costs $2^{n}$ formula evaluations, exponential time, and every added variable doubles the work.

Sense-check: the count grows by a factor of two per variable — $n = 3$ gives 8, $n = 4$ gives 16, $n = 5$ gives 32 — which is the defining behaviour of exponential growth.

12.18.4 SAT as a Non-deterministic Algorithm

SAT is in NP, and here is the non-deterministic algorithm that proves it. First phase: a choice function guesses a truth assignment — $x_{0}$ is 0, $x_{1}$ is 1, $x_{2}$ is 1, say — with no guarantee about which assignment it produces or how it produces it. Second phase: given the guessed assignment, evaluate the formula. If all the clauses evaluate to 1, the formula is satisfied; otherwise it is not. Evaluating clauses is quick — polynomial time. The guessing phase is non-deterministic; only the verification is polynomial, which is exactly the definition of NP. The pattern is always the same: the guessing phase is what we want somebody else to figure out.

SAT in NP — the guess-and-verify proof. The certificate is a truth assignment: one bit per variable. The verifier plugs the assignment into each clause — each clause check is proportional to its length, and the total evaluation is proportional to the formula size — so verification is polynomial time. With the guess in hand and the polynomial check in place, SAT satisfies the definition of NP exactly.

The warning from the session: the guessing phase is non-deterministic and the verification phase is polynomial time — keep those two labels attached to the right phases, because confusing them is the classic slip on this topic.

12.18.5 Student Questions and Answers

Q: How does a machine actually find the satisfying assignment? Does it check assignments cleverly? A: It does not need to. In the NP framework the machine does not find anything cleverly: the choice function guesses the assignment, and we only verify the guess in polynomial time. Finding the assignment is the part left open — that is precisely why SAT is a hard problem, and why the guessing phase is the piece somebody has to explain someday.

Recap + bridge: SAT asks whether some 0/1 assignment makes a formula true; CNF gives the formula a standard shape (AND of OR-clauses), brute force costs $2^{n}$ , and the guess-and-verify proof places SAT in NP. SAT's central position is sealed by the next section's definitions: NP hard and NP complete.

12.19 NP Hard and NP Complete

12.19.1 Reductions: If One is Solved, All are Solved

Two more terms close the classification: NP hard and NP complete. Both rest on reductions. Suppose we have a new problem and cannot write a polynomial time algorithm for it. What do we do? We do the shared-blame move: we show that an existing NP problem reduces to our problem. "Reduces" here means we show the two problems are equivalent — the new problem can be expressed in terms of the old one, in such a way that a solution to one gives a solution to the other. If satisfiability reduces to 0/1 knapsack, then whoever solves satisfiability later has also solved our 0/1 knapsack problem. One solved, all solved. That is the entire engine of the theory: any NP problem that gets pulled into P pulls everything connected to it along.

Definition (polynomial-time reduction): problem $A$ reduces to problem $B$ in polynomial time, written $A \leq_{P} B$ , when there is a polynomial-time procedure that turns every instance of $A$ into an instance of $B$ such that the answers match — the transformed instance of $B$ is a yes-instance exactly when the original instance of $A$ was. Because the transformation is polynomial, a polynomial algorithm for $B$ would immediately give a polynomial algorithm for $A$ : transform, then solve.

Why reductions are the engine of the theory: they carry solutions along them. If $A \leq_{P} B$ and $B$ is in P, then $A$ is in P. The flow of difficulty runs from the easier problem to the harder one — a solution for the target solves the source, so the target is at least as hard as the source.

12.19.2 NP Hard

When we reduce an existing NP problem to our new problem, our problem becomes NP hard: it is at least as hard as an NP problem. If satisfiability — already proven to be an NP problem — reduces to 0/1 knapsack, then 0/1 knapsack is at least as hard as satisfiability, and it earns the label NP hard. One successful reduction is enough; the textbook ideal is to show that all NP problems reduce to your problem, but any single reduction already proves the hardness.

Definition (NP hard): a problem is NP hard when every problem in NP reduces to it (equivalently in practice: when some known NP problem reduces to it). It is at least as hard as everything in NP — if it were solvable in polynomial time, every NP problem would be too. Note the direction: the known NP problem reduces to the new problem, carrying the hardness in.

12.19.3 NP Complete

A problem is NP complete when it is both in NP and NP hard. Getting from "new problem" to "NP complete" is a two-step climb. Step one: write a non-deterministic polynomial time algorithm for the problem — that alone makes it merely NP. Step two: reduce one of the other NP problems to it — that makes it NP hard. Both steps together, the problem sits inside the NP circle and at least as high as the circle: NP complete. Picture the classes as circles: the NP circle contains P; NP hard problems lie at or above the level of NP; and NP complete is the overlap — in NP, and as hard as anything in it.

Definition (NP complete): a problem is NP complete when it is both in NP and NP hard — the hardest of the easy-to-verify problems. The two-step proof recipe: (1) show it is in NP via a guess-and-verify algorithm; (2) show it is NP hard by reducing a known NP problem to it. Every NP complete problem is equivalent in difficulty to every other: a polynomial algorithm for any one of them would put the whole of NP into P.

The circle picture: the NP circle contains the P circle inside it. NP hard problems are at least as hard as everything in the NP circle — they lie at or above its rim. NP complete problems are exactly the ones on the rim of the NP circle: inside it (they are NP) and at its hardest level (they are NP hard).

12.19.4 Worked Example: Satisfiability Reduces to 0/1 Knapsack

The class worked the idea on satisfiability and 0/1 knapsack. A CNF satisfiability formula with three literals, $x_{0}, x_{1}, x_{2}$ , is equivalent to a knapsack problem with three objects. Every assignment of the three literals is a choice about the three objects: take object 1 or not, take object 2 or not, take object 3 or not — try all possibilities until a satisfying solution is found. Because satisfiability is a known NP problem and it reduces to 0/1 knapsack, the knapsack problem is NP hard. And 0/1 knapsack was already known to be solvable in pseudo-polynomial time $O (nW)$ — the class had seen it earlier in the session — which makes knapsack such an instructive example.

Worked example — CNF satisfiability reduces to 0/1 knapsack.

The setup: a CNF formula on three literals $x_{0}, x_{1}, x_{2}$ — say $(x_{0} \lor x_{1} \lor x_{2}) \land (\neg x_{0} \lor x_{1} \lor \neg x_{2})$ .

Step 1 — build the knapsack instance: three objects, one per literal. Object $i$ stands for literal $x_{i}$ ; the weight and value are chosen so that taking object $i$ means "set $x_{i} = 1$ " and skipping it means "set $x_{i} = 0$ ", with the capacity and values engineered to admit a satisfying subset exactly when a satisfying assignment exists.

Step 2 — translate the question: "is there an assignment making the formula true?" becomes "is there a subset of the three objects that fits the knapsack and meets the value bound?" — the decision version of knapsack. Every assignment of the three literals is a choice about the three objects: take object 1 or not, take object 2 or not, take object 3 or not.

Step 3 — read off the consequence: the transformation is polynomial (three objects from three literals), so satisfiability $\leq_{P}$ 0/1 knapsack. Since satisfiability is a known NP problem, 0/1 knapsack is NP hard.

Final answer: 0/1 knapsack is NP hard — and it was already known to be in NP, so it is NP complete — while remaining solvable in pseudo-polynomial time $O (nW)$ , which is why the class calls it such an instructive example: NP hard does not mean unsolvable in practice for small values.

Sense-check: the reduction direction is right — the known NP problem (satisfiability) reduces to the new problem (knapsack), so hardness flows into knapsack; a polynomial algorithm for knapsack would solve satisfiability, and via the reduction web, all of NP.

12.19.5 Student Questions and Answers

Q: Why do we keep inviting new problems into the theory? Are the old problems not enough? A: New problems arrive whether we invite them or not — real problems from real applications need solving. The theory gives us the tool for dealing with any new problem we cannot solve: relate it to the problems we already know, so that progress on the known ones carries over. The old problems are not "enough"; they are the anchors that let us place every new problem.

Pitfalls:

Getting the reduction direction backwards: the known NP problem must reduce to the new problem. Reducing the new problem to a known NP problem proves the new problem is easy, not hard.
Calling a problem NP complete on the strength of NP hardness alone: membership in NP is the other required half.
Believing NP hard means "impossible in practice": the label says no polynomial algorithm is known; algorithms with pseudo-polynomial time (like $O (nW)$ knapsack) or exponential time with good pruning are still used every day.

Recap + bridge: reductions carry solutions between problems; NP hard means at least as hard as NP; NP complete means NP hard plus in NP — the two-step climb of membership then reduction. The reduction machinery now points at the problem at the centre of everything: satisfiability, whose special position is fixed by Cook's theorem.

12.20 Cook's Theorem and Proving SAT is NP Complete

12.20.1 Cook's Theorem

The satisfiability problem has a special historical position, captured by Cook's theorem: NP becomes equal to P if and only if the satisfiability problem is in P. The reason is the reduction web — since every NP problem reduces to SAT, solving SAT in polynomial time solves all of NP in one blow. There are many problems still sitting in NP, and we are all waiting for that first moment when somebody shows one of them can be solved in P time; the moment that happens, the reduction connections carry every other NP problem into P with it.

Cook's theorem: SAT is NP complete — it is in NP, and every problem in NP reduces to it in polynomial time. The consequence is the famous equivalence

$P = N P ⟺ SAT is in P$

If SAT has a polynomial time algorithm, then every NP problem does (reduce to SAT, then solve); if SAT does not, then no NP complete problem does. One problem, stated in a single sentence, is the pivot on which the whole classification turns.

Why the theorem matters historically: it gave the field its first certified NP complete problem. Before Cook's theorem, NP hardness claims had nothing to reduce from; after it, every new problem could be shown hard by reducing SAT to it — the starting point of the reduction web.

12.20.2 Proving SAT is in NP

To prove SAT is NP complete, show the two halves separately. Half one: SAT is in NP. Write the non-deterministic algorithm — the guessing part hands over an assignment like $x_{1} = 0, x_{2} = 1, x_{3} = 1$ , and the verification part evaluates the formula in polynomial time. Since verification is polynomial and the guessing part is non-deterministic, SAT is an NP problem.

Half one of the proof — SAT is in NP. The certificate is a truth assignment (one bit per variable). The verifier plugs the assignment into the formula and evaluates; the work is proportional to the size of the formula, so the check is polynomial time. A guess plus a polynomial check is exactly the definition of NP membership — the same pattern used for the MST decision problem earlier.

12.20.3 Proving SAT is NP Hard

Half two: SAT is NP hard. Take an existing NP problem and reduce it to SAT. The classic choice is the circuit satisfiability problem: given a circuit built of AND and OR logic gates, is it satisfiable? Circuit satisfiability was the original problem studied when machine circuits first appeared, and it is known to be NP. Showing that circuit satisfiability reduces to SAT — in polynomial time — proves SAT is NP hard. The reduction is natural to see: circuits are made of literals and AND/OR gates, which are exactly the pieces a CNF formula is built from, so a circuit can be translated into an equivalent formula. Both halves proven, SAT is both NP and NP hard, and so NP complete.

Worked example — circuit satisfiability reduces to SAT.

The source problem: a circuit built of AND and OR logic gates with input wires and one output wire — is there an assignment of 0/1 to the inputs that makes the output 1? This is the circuit satisfiability problem, known to be in NP.

Step 1 — translate gate by gate. Every gate computes one output from its inputs, and every gate's behaviour can be written as a small CNF clause set: an AND gate $z = x \land y$ is true under exactly the assignments where the clause set for $(z ⟺ x \land y)$ holds, and an OR gate $z = x \lor y$ likewise. The translation walks the circuit once, so it runs in polynomial time in the circuit size.

Step 2 — combine the pieces. AND together the clause sets of all gates, then add the single-literal clause that forces the output wire to 1. The resulting CNF formula is satisfiable exactly when the circuit has an input assignment making its output 1.

Step 3 — read off the consequence: circuit satisfiability $\leq_{P}$ SAT in polynomial time, so SAT is NP hard. With the in-NP half already shown, SAT is NP complete.

Final answer: the reduction is natural because circuits are built from literals and AND/OR gates — the same pieces a CNF formula is built from — so a circuit translates into an equivalent formula, and the hardness of circuit satisfiability carries over to SAT.

Sense-check: the translation preserves answers in both directions — a satisfying input of the circuit gives a satisfying assignment of the formula, and a satisfying assignment of the formula gives a circuit input with output 1 — which is precisely what a correct reduction requires.

Pitfalls:

Reducing SAT to circuit satisfiability and claiming hardness for SAT: the reduction must go from the known NP problem (circuit satisfiability) to the target (SAT), not the other way.
Forgetting that Cook's theorem already proved the "every NP problem reduces to SAT" direction — later NP hardness proofs only need one known NP complete problem to reduce from.
Treating the two halves of NP completeness as optional: in NP alone proves nothing about hardness; NP hard alone does not place the problem in NP.

12.20.4 Terminology Contrast: Implication vs Reduction

Q: Some students confused the implies symbol with the reduction symbol. What is the difference between the "implies" arrow and the reduction symbol with P? A: The plain implies arrow connects statements in logic: the left hand side implies the right hand side, and it says nothing about computation. The reduction symbol with P — "reduces to in polynomial time" — is a different, stronger claim: it says one problem can be transformed into another so that solving one solves the other, and the transformation takes polynomial time. Do not let the two symbols blur together; one is logic, the other is computational equivalence.

Recap + bridge: Cook's theorem pins SAT at the centre — $P = N P$ exactly when SAT is in P — and the two-half proof (in NP by guess-and-verify, NP hard by reducing circuit satisfiability) is the template for every NP completeness proof after it. With the classification complete, the session closes by looking at the problems still waiting and what solving one of them would mean.

12.21 Open Problems and Research Directions

12.21.1 Problems Still Waiting

The classification is not closed; it is an active research area with open problems at every level. The clique problem is one example: a clique is a complete graph — every pair of vertices connected — and finding cliques has applications in machine learning and data mining. Tower of Hanoi, the traveling salesperson problem (TSP), and many others still have no polynomial time solutions. Each is a standing invitation: take the clique problem and try to find a linear time algorithm for it; take TSP; take Tower of Hanoi. There is still a lot of scope for research in these problems.

Definition (clique): a clique is a subset of vertices of a graph in which every pair of vertices is connected by an edge — a complete subgraph. The clique decision problem asks whether the graph contains a clique of a given size; no polynomial time algorithm is known, and the problem is a standard member of the NP complete family with practical uses in machine learning and data mining.

The standing invitation list: clique, TSP, Tower of Hanoi, and the many other NP complete problems are open invitations to research — each asks for the polynomial time algorithm nobody has found yet, and each carries the same reward through the reduction web: solving any one solves them all.

Real-world connection: the clique problem appears in social network analysis (finding groups where everyone knows everyone), in bioinformatics (finding sets of proteins that all interact), and in data mining (finding highly correlated feature subsets). TSP is the model behind route-planning and logistics optimization — delivery fleets, circuit-board drilling, and vehicle routing all solve TSP-like problems daily with good heuristics, precisely because the exact optimal route is NP hard to certify.

12.21.2 What the First Solution Would Mean

The shared structure means the whole field waits on a single first result. The moment anybody shows that one NP problem can be solved in P time, the reductions guarantee every other NP problem falls into P as well — NP equals P, and the biggest open question in computer science is answered. That is why the problem list matters and why the classification exists: to preserve everything we already know, to connect everything we do not, and to define exactly what solving the hard ones would mean.

The warning from the session: the moment the first NP problem is brought into P, every other NP problem is pulled into P along the reduction connections — one solved, all solved. Keep that single-trigger structure in mind: it is why the whole field watches the same short list of problems, and why a breakthrough on any one of them is a breakthrough on all of them.

Recap + bridge — closing the course: this session opened with matrix chain product, where dynamic programming pulled an exponential search down to $O (n^{3})$ ; it closes with the classification that explains what such a rescue means in general — problems whose answers are easy to check (NP) and problems whose answers are hard to find, with P = NP as the grand open question. The matrix chain product is a concrete success story of exactly the research program the classes exist to organize.

Exam Guidance Summary

Complexity classes carry small weight: at most two or three marks, and possibly no question at all, even though the topic is part of the final syllabus and the recorded lecture videos are part of the course. Do understand the ideas anyway — they are simple once the mental block is removed.

Exam note: for matrix chain product, expect a question of the form "deduce $M [1, 4]$ " for a chain of four matrices — the exact version worked in this session — and the same question may come with five or six matrices, where the same table procedure runs one or two steps further. Write out the full $M$ and $S$ tables and the final parenthesization; the computation is lengthy, and the paper itself may be lengthy, because matrix chain product, MST, and shortest path questions are all lengthy to write.

Exam note: end semester is not as difficult as the mid-semester was. The post-mid-semester material is algorithm design strategies, which is comparatively easy if the basic concepts are understood — but the paper may be long, so manage time.

Exam note: expect conceptual questions on P and NP — the definitions, the satisfiability problem, and the P equals NP question are the natural short-answer territory for the small weight this topic carries.

Sample questions that were shown as possible exam material:

Quicksort is implemented by choosing a random index for the pivot. Will this completely avoid the worst case? Justify.
When a linked list stores the input elements to sort, which of merge sort and quicksort is preferred? Justify.
Longest palindromic subsequence inside a string — which algorithm design strategy is used, and what is the running time of the algorithm? (This was also an exercise earlier in the course.)
A "justify" style question — several students wrote this one in the mid-semester.
Compute the shortest path between all pairs of vertices. Note: all pairs shortest path is not Dijkstra's algorithm — the all-pairs-shortest-path material was uploaded separately; check it.
A chain of four matrices $B_{1}$ to $B_{4}$ — deduce $M [1, 4]$ .
A small procedure is given — identify what the algorithm does. This type appeared in one of the makeup exams.

Guidance from the close of the session: be thorough with all the design strategies and all the algorithms covered in class; questions are picked from almost all the topics, so every covered topic should be expected to appear. The quiz has no makeup — do not miss it. On workload: the weightage asked from pre-mid-semester topics may be reduced; focusing only on the post-mid-semester topics may be enough to pass — but that is "may", not certainty: if other students study everything thoroughly, relative grading can push your grade down. The recorded lecture videos are part of the course, so reviewing them is not optional.

Time management: the paper can be long, and the lengthy computations (matrix chain product, MST, shortest paths) take writing time on top of thinking time. Practise the table-filling procedures to speed; leave the short conceptual questions for the end if the long ones run over.

Key Industry Applications

Matrix multiplication is everywhere in modern data science — principal component analysis (PCA) and support vector machines (SVM), both used heavily in machine learning and data mining, are built on matrix operations whose cost follows exactly the counting rules of this session.

Natural language processing (NLP) has documented applications of matrix chain product, listed in the course notes; the standing takeaway is that the technique has extensive application in today's data science work.

Network analysis and circuit analysis use the same chain-product structure — ABCD matrices in electrical circuits compute the voltage across a chain of components, and multiplying those transmission matrices in a good order is a matrix chain product.

Real-world: data science pipelines. PCA computes eigendecompositions of covariance matrices; SVM solves quadratic programs over kernel matrices; both reduce to repeated matrix products, and every framework that evaluates a product of several matrices picks its bracket order with exactly the cost rule of this session. The technique is not a textbook toy — it is the arithmetic underneath a modern machine learning stack.

Real-world: networks and circuits. ABCD transmission matrices chain the voltage behaviour of circuit components, and the best order to multiply them is a matrix chain product; the same chain-product structure appears in network analysis. Knowing how to order the multiplications is a concrete engineering payoff of the algorithm.

The complexity classes are not only theory — P versus NP is one of the Millennium Prize problems, a funded open research question. The clique problem connects to machine learning and data mining, and TSP is the model behind route-planning and logistics optimization.

Real-world: optimization at scale. Delivery fleets, vehicle routing, circuit-board drilling, and logistics software solve TSP-style problems daily with fast heuristics and approximation algorithms, because the exact optimum is NP hard to certify. Understanding the classes explains why those heuristics exist: for these problems, a guaranteed polynomial exact algorithm is precisely what P = NP would deliver — and until then, the practical answer is near-optimal search.

DSA Lecture 12 notes · Matrix Chain Multiplication and Complexity Classes

Data Structures and Algorithms· postgraduate· 2026-08-09

Sections Breakdown

1Where We Left Off: Dynamic Programming

Recap of 0/1 knapsack and its pseudo-polynomial dynamic programming solution, plus the session plan.

2Matrix Multiplication Basics

The school algorithm for multiplying matrices and the p·q·r scalar multiplication cost rule.

3The Matrix Chain Product Problem

Associativity, parenthesizations, and the statement of the matrix chain product problem.

4Why Brute Force Fails: Catalan Numbers

Counting parenthesizations with Catalan numbers and their roughly 4ⁿ growth.

5Input Representation and Notation

The dimension array D₀..Dₙ and the A[i..j] subchain notation.

6The Dynamic Programming Tables and Recurrence

The M cost table, the S split table, and the recurrence with its optimal substructure.

7Worked Example: Dimensions 5, 4, 6, 2, 7

A full table-filling run giving M[1,4] = 158.

8Reading the Parenthesization Back

Reconstructing the optimal parenthesization from the S table and verifying the multiplication sequence.

9Time Complexity of Matrix Chain Product

Why three nested loops give O(n³) time and O(n²) space.

10Applications of Matrix Chain Product

Where chain products appear: PCA, SVM, NLP pipelines, and circuit analysis.

11Why Study Complexity Classes?

The research program behind P and NP and the shared-blame analogy.

12Decision Problems and Optimization Problems

Yes/no decision problems, optimization problems, and the parameter-k conversion.

13Class P: Polynomial Time

The definition of P and why polynomial time is the boundary that matters.

14Deterministic and Non-deterministic Algorithms

Choice functions and the guess-and-verify two-phase structure.

15Class NP: Non-deterministic Polynomial Time

The definition of NP and the sorting story of a problem leaving NP.

16P ⊆ NP and the P = NP Question

The one-sided inclusion and the most famous open question in computer science.

17Proving a Problem is in NP

Certificates and polynomial-time verifiers, with the MST of weight k example.

18The Satisfiability Problem

SAT, conjunctive normal form, brute force 2ⁿ, and SAT in NP.

19NP Hard and NP Complete

Reductions, NP hardness, and the two-step NP completeness proof.

20Cook's Theorem and Proving SAT is NP Complete

Cook's theorem and the two-half proof via circuit satisfiability.

21Open Problems and Research Directions

Clique, TSP, Tower of Hanoi, and what the first solution would mean.

22Exam Guidance Summary

The professor's exam strategy for matrix chain product and complexity classes.

23Key Industry Applications

Real-world uses of matrix chain products and complexity theory.

Postgraduate students in Artificial Computational Intelligence

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Where We Left Off: Dynamic Programming

Must-know: 0/1 knapsack is solved by dynamic programming in O(nW) time, which is pseudo-polynomial because it depends on the numeric value of W, while brute force is O(2^n).

$O (nW) vs O (2^{n})$

Top pitfall: Calling the O(nW) knapsack algorithm truly polynomial: it is pseudo-polynomial because W is a numeric value, not a count of input items.

Self-check: Why is the time bound of dynamic programming knapsack called pseudo-polynomial?

Connects to: Why Brute Force Fails: Catalan Numbers, Class P: Polynomial Time, P ⊆ NP and the P = NP Question

Matrix Multiplication Basics

Must-know: A p by q matrix times a q by r matrix costs p times q times r scalar multiplications and produces a p by r matrix; the middle dimension cancels.

$cost (A_{p \times q} \cdot B_{q \times r}) = p \cdot q \cdot r$

Top pitfall: Writing the result shape as the inner pair of dimensions; the result is always the outer pair p by r.

Self-check: A 2 by 3 matrix times a 3 by 2 matrix: how many scalar multiplications and what result shape?

Connects to: The Matrix Chain Product Problem, Input Representation and Notation

The Matrix Chain Product Problem

Must-know: The matrix chain product problem asks only for the cheapest parenthesization of a product, never for the product itself; (B·C)·D cost 1575 while B·(C·D) cost 4000 for the same three matrices.

Top pitfall: Splitting a chain into overlapping pieces that repeat a matrix; valid splits are always A[i..k] followed by A[k+1..j].

Self-check: Why do two parenthesizations of the same three matrices need different numbers of scalar multiplications?

Connects to: Matrix Multiplication Basics, Why Brute Force Fails: Catalan Numbers, The Dynamic Programming Tables and Recurrence

Why Brute Force Fails: Catalan Numbers

Must-know: A chain of n matrices has C_(n-1) = (1/n) C(2n-2, n-1) parenthesizations, growing almost like 4^n, which makes brute force hopeless.

$C_{n - 1} = \frac{1}{n} (n - 1 2 n - 2)$

Top pitfall: Writing C_n for a chain of n matrices instead of C_(n-1), or confusing the count with 2^n.

Self-check: How many parenthesizations does a chain of four matrices have?

Connects to: The Matrix Chain Product Problem, The Dynamic Programming Tables and Recurrence, Time Complexity of Matrix Chain Product

Input Representation and Notation

Must-know: A chain of n matrices is given by n+1 dimensions D_0..D_n with A_i of order D_(i-1) by D_i; every subchain A[i..j] splits as A[i..k] A[k+1..j].

$A [i .. j] = A [i .. k] \cdot A [k + 1.. j], i \leq k < j$

Top pitfall: Reading A[1..1] as the square of A1: it is the single matrix A1 with zero cost.

Self-check: If the input array is 10, 20, 30, 40, 50, what is the order of A2?

Connects to: Matrix Multiplication Basics, The Dynamic Programming Tables and Recurrence

The Dynamic Programming Tables and Recurrence

Must-know: M[i,j] is the minimum cost of A[i..j]; the recurrence adds the two subchain minima to the join cost D_(i-1) D_k D_j and takes the best k; S[i,j] records that k.

$M [i, j] = i \leq k < j min (M [i, k] + M [k + 1, j] + D_{i - 1} \cdot D_{k} \cdot D_{j}), M [i, i] = 0$

Top pitfall: Filling the table by guessed importance instead of chain length, or updating M without updating S.

Self-check: Why is the join cost for split k equal to D_(i-1) times D_k times D_j?

Connects to: Input Representation and Notation, Worked Example: Dimensions 5, 4, 6, 2, 7, Reading the Parenthesization Back

Worked Example: Dimensions 5, 4, 6, 2, 7

Must-know: For dimensions 5, 4, 6, 2, 7, the minimum is M[1,4] = 158 via split k = 3; fill length-2 chains, then length-3, then the whole chain, updating S with every M minimum.

Top pitfall: Suggesting the cheapest-looking pair as the smallest subproblem — the smallest subproblem is always a single matrix, and S records the winning split, not a preferred value.

Self-check: Why does split k = 3 win for M[1,4] in the example, and what is its total?

Connects to: The Dynamic Programming Tables and Recurrence, Reading the Parenthesization Back, Time Complexity of Matrix Chain Product

Reading the Parenthesization Back

Must-know: Walk S from S[1,n] recursively: split at k = S[i,j] into A[i..k] and A[k+1..j] until single matrices remain; the example gives (A1(A2A3))A4 with total cost 48 + 40 + 70 = 158.

$(A_{1} \cdot (A_{2} \cdot A_{3})) \cdot A_{4}$

Top pitfall: Stopping after the first split, or trying to reconstruct the grouping from the M cost values instead of the S split positions.

Self-check: Starting from S[1,4] = 3 and S[1,3] = 1, what parenthesization does the S table produce?

Connects to: The Dynamic Programming Tables and Recurrence, Worked Example: Dimensions 5, 4, 6, 2, 7

Time Complexity of Matrix Chain Product

Must-know: The chain-length, start-position, and split-position loops each run to the order of n, so matrix chain product runs in O(n^3) time with O(n^2) space; three loops alone do not guarantee n cube — the bounds must each be order n.

$O (n^{3})$

Top pitfall: Saying three loops always mean n cube; the justification is that each loop runs to the order of n.

Self-check: Why is the time complexity O(n^3) rather than O(n^2), and what is the space complexity?

Connects to: Why Brute Force Fails: Catalan Numbers, The Dynamic Programming Tables and Recurrence, Class P: Polynomial Time

Applications of Matrix Chain Product

Must-know: The p times q times r cost rule governs matrix products everywhere in data science — PCA, SVM, NLP pipelines — and in circuit analysis via ABCD transmission matrices.

Self-check: Name two data science tools whose computations follow the matrix multiplication cost rules.

Connects to: Matrix Multiplication Basics

Why Study Complexity Classes?

Must-know: Complexity classes preserve the work of the research program that tries to move exponential-time problems into polynomial time; relating an unsolved problem to a known hard one is the start of the theory of reductions.

Top pitfall: Believing the topic cannot be understood before starting; the session names this mental block as the real obstacle.

Self-check: What does the shared-blame analogy say about TSP and Tower of Hanoi?

Connects to: NP Hard and NP Complete, Open Problems and Research Directions

Decision Problems and Optimization Problems

Must-know: Introducing a parameter k turns any optimization problem into a decision problem: TSP becomes 'is there a Hamiltonian cycle of weight at most k?', knapsack becomes 'is there a subset with value at least k?'; decision answers for all k locate the optimum.

Top pitfall: Using 'at most' for maximization problems: maximizations use 'at least k', minimizations use 'at most k'.

Self-check: What is the decision version of the traveling salesperson problem?

Connects to: Class P: Polynomial Time, Proving a Problem is in NP, The Satisfiability Problem

Class P: Polynomial Time

Must-know: P contains the problems solvable in time O(n^k) for some constant k, where n is the size of the input; search O(n), sorting O(n log n) are in P, brute force knapsack O(2^n) is not.

$T (n) = O (n^{k}), k a constant$

Top pitfall: Taking n as the number of operations or allowing an exponent that grows with n; n is the input size and k is a constant.

Self-check: Why is an O(n log n) sorting algorithm a member of class P?

Connects to: Where We Left Off: Dynamic Programming, P ⊆ NP and the P = NP Question, Deterministic and Non-deterministic Algorithms

Deterministic and Non-deterministic Algorithms

Must-know: A non-deterministic algorithm guesses a candidate solution with a choice function, then verifies it in polynomial time; search is the running example, and the framework exists so that work on unsolved problems is not lost.

Top pitfall: Reading non-determinism as randomness; the guess is an unspecified but guaranteed correct candidate, and the verification phase is what makes the algorithm meaningful.

Self-check: What are the two phases of a non-deterministic algorithm?

Connects to: Class NP: Non-deterministic Polynomial Time, Proving a Problem is in NP

Class NP: Non-deterministic Polynomial Time

Must-know: NP = non-deterministic polynomial time: a problem is in NP when a guess plus a polynomial-time check solves it; the N stands for non-deterministic, and sorting left NP for P when merge sort and quicksort explained the choice function.

Top pitfall: Expanding NP as non-polynomial; the correct expansion is non-deterministic polynomial time.

Self-check: Say the full meaning of NP, and give the sorting story in one sentence.

Connects to: Deterministic and Non-deterministic Algorithms, P ⊆ NP and the P = NP Question, Proving a Problem is in NP

P ⊆ NP and the P = NP Question

Must-know: P ⊆ NP is proven (replace deterministic logic by a choice function and verify with the original algorithm); P = NP is open, a Millennium Prize problem, and one NP problem in P would collapse all of NP into P.

$P \subseteq N P$

Top pitfall: Reading NP membership as a hardness claim; every P problem is also in NP.

Self-check: Why does proving one NP problem solvable in polynomial time settle P = NP?

Connects to: Class P: Polynomial Time, Class NP: Non-deterministic Polynomial Time, NP Hard and NP Complete

Proving a Problem is in NP

Must-know: To prove NP membership, either show the problem is in P, or define a certificate and a polynomial-time verifier; the MST decision problem certifies n-1 edges and checks them in O(n+m) time.

$O (n + m)$

Top pitfall: Guessing without a concrete certificate, or accepting a verifier that runs in non-polynomial time.

Self-check: What does the verifier check for the MST-of-weight-k decision problem?

Connects to: Deterministic and Non-deterministic Algorithms, Class NP: Non-deterministic Polynomial Time, The Satisfiability Problem

The Satisfiability Problem

Must-know: SAT is the first known NP problem: is there a 0/1 assignment making the formula true? In CNF (AND of r clauses, each an OR of literals) brute force tries 2^n assignments, and guessing plus polynomial-time evaluation proves membership in NP.

$2^{n} possible assignments$

Top pitfall: Confusing the phases: the guess is non-deterministic, the verification is polynomial time.

Self-check: Why is brute force SAT exponential, and what is the certificate the verifier checks?

Connects to: Class NP: Non-deterministic Polynomial Time, Proving a Problem is in NP, NP Hard and NP Complete

NP Hard and NP Complete

Must-know: Reduce a known NP problem to a new problem to make it NP hard; prove it is in NP as well to make it NP complete; satisfiability reduces to 0/1 knapsack, so knapsack is NP hard despite its pseudo-polynomial O(nW) algorithm.

$A \leq_{P} B \Rightarrow (B \in P \Rightarrow A \in P)$

Top pitfall: Reversing the reduction direction: the known NP problem must reduce to the new problem, otherwise hardness does not flow into it.

Self-check: What are the two steps that make a problem NP complete?

Connects to: P ⊆ NP and the P = NP Question, The Satisfiability Problem, Cook's Theorem and Proving SAT is NP Complete

Cook's Theorem and Proving SAT is NP Complete

Must-know: Cook's theorem: NP = P if and only if SAT is in P. Proving SAT NP complete needs two halves: in NP (guess an assignment, verify in polynomial time) and NP hard (reduce circuit satisfiability to SAT in polynomial time).

$P = N P ⟺ SAT is in P$

Top pitfall: Confusing the implies arrow (logic) with the reduction symbol ≤_P (polynomial-time transformation), or reducing in the wrong direction.

Self-check: What are the two halves of the proof that SAT is NP complete?

Connects to: The Satisfiability Problem, NP Hard and NP Complete, Open Problems and Research Directions

Open Problems and Research Directions

Must-know: Clique, TSP, and Tower of Hanoi have no known polynomial time algorithms; because every NP problem reduces to every other, the first NP problem solved in P time pulls all of NP into P.

Top pitfall: Treating the classification as finished; it is an active research area, and the open problems are standing research invitations.

Self-check: What happens to all NP problems the moment one NP problem is solved in polynomial time?

Connects to: P ⊆ NP and the P = NP Question, NP Hard and NP Complete, Cook's Theorem and Proving SAT is NP Complete

Exam Guidance Summary

Must-know: Expect a four-matrix M[1,4] deduction with full M and S tables and the final parenthesization; complexity classes carry at most two or three marks with conceptual questions on definitions, SAT, and P = NP; the end semester paper is long, so manage time.

Top pitfall: Leaving the lengthy table computations for the last minutes; the paper is long and the writing itself takes time.

Self-check: What form does the matrix chain product exam question take?

Connects to: Worked Example: Dimensions 5, 4, 6, 2, 7, Time Complexity of Matrix Chain Product, P ⊆ NP and the P = NP Question

Key Industry Applications

Must-know: The p·q·r cost rule sits under PCA, SVM, NLP, and ABCD-matrix circuit analysis; P versus NP is a Millennium Prize problem, clique connects to machine learning and data mining, and TSP models route-planning and logistics optimization.

Self-check: Where does the chain-product structure appear in electrical engineering?

Connects to: Matrix Multiplication Basics, Applications of Matrix Chain Product, P ⊆ NP and the P = NP Question

Previous LectureLecture 11 · Minimum Spanning Trees and Dynamic Programming

Next LectureLecture 01 · Introduction to Data Visualization

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.