Complexity Atlas
HE
Interactive gallery

Visualization gallery

42 interactive visualizations from the lessons and exercises, collected in one place.

Foundations and machine models

4 visualizations

Compare logarithmic, polynomial, and exponential growth as the input size changes.

Guided construction

Growth-rate map

Step 1 of 6
Growth-rate comparisonCurves for log n, n, n log n, n squared, and two to the n on a linear vertical scale.01,0242,0483,0724,09624681012input size nfunction value (linear scale)log₂ n
log₂ n
Study next

Trace a deterministic machine through configurations while tracking its space usage.

Guided construction

Deterministic configuration graph

Step 1 of 7
Input x=1010Invariant: state records parity of the 1s already scannedδ(q_even, 1) = (q_odd, R)
Deterministic parity-machine configuration pathSix configurations form one path. Each nonhalting configuration has exactly one outgoing transition.q_evenhead = 0scans 1[1] 0 1 0 □
q_evenhead position 0 · scanned symbol 1
1
0
1
0
□
Unique next moveδ(q_even, 1) = (q_odd, R)
visited configurationunique legal transitioncurrent head position
Study next

Follow an accepting choice sequence through a branching computation and read it as a certificate.

Guided construction

Nondeterministic computation tree

Step 1 of 7
φ =(x₁ ∨ ¬x₂)∧(x₂ ∨ x₃)
Binary nondeterministic computation treeThe verifier guesses three assignment bits. Eight leaves check the formula, and the path 110 reaches an accepting leaf.ε
legal binary choice
Study next
Practise it

Place P, NP, and coNP using only known containments while keeping open equalities explicit.

Guided construction

NP and coNP

Step 1 of 6
Known: P⊆NP
Known containments among P, NP, and coNPDashed schematic NP and coNP boundaries overlap. P is contained in their intersection. SAT and UNSAT show known certificate memberships, while P versus NP and NP versus coNP remain open.NPshort yes-certificates
schematic class boundary
Study next

Reductions and encodings

24 visualizations

Build clause gadgets, add conflict edges, choose the threshold, and prove both directions.

Guided construction

3SAT → Independent Set

Step 1 of 7
φ =(x ∨ y ∨ z)∧(¬x ∨ y ∨ w)∧(¬y ∨ z ∨ w)
3SAT to Independent Set constructionThree clause panels become triangle gadgets. Solid edges join literals in one clause, dashed edges join complementary literals, and the final step selects x, y, and z as an independent set of size three.C1x ∨ y ∨ zsource clauseC2¬x ∨ y ∨ wsource clauseC3¬y ∨ z ∨ wsource clause
Same-clause edgeComplement conflict
Study next
Practise it

Flip every non-edge into an edge, keep the same vertex set and threshold, and read an independent set as a clique.

Guided construction

Independent Set → Clique

Step 1 of 6
Independent Set to Clique via graph complementA path on four vertices is complemented; an independent pair becomes a clique while the threshold stays k.Source G1234Complement Ḡ1234
Original edge (removed)Complement edge (added)
Study next
Practise it

Keep the same graph, complement the chosen vertex set, and send the threshold k to |V|−k.

Guided construction

Independent Set → Vertex Cover

Step 1 of 6
Independent Set to Vertex Cover via set complementAn independent set on a path is complemented to a vertex cover while the threshold becomes n minus k.Same graph G1234
Study next
Practise it

Split a long CNF clause into an equisatisfiable chain of triples using fresh variables, without exponential distributivity.

Guided construction

SAT → 3SAT

Step 1 of 6
Source clause(a ∨ b ∨ c ∨ d ∨ e)
SAT to 3SAT by clause splittingA five-literal clause is replaced by three overlapping triples linked by two fresh variables.Source clause
Fresh variableOutput triple
Study next
Practise it

Place literal vertices, cut every variable pair, score two edges per clause triangle, and meet threshold n+2m.

Guided construction

NAE-3SAT → Max-Cut

Step 1 of 7
Source NAE-3CNF(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)
NAE-3SAT to multigraph Max-CutLiteral vertices with variable edges and clause triangles; a cut of size n+2m encodes an NAE assignment.Source NAE-3CNF
Variable edgeClause edge
Study next
Practise it

Complete the graph, price original edges 1 and missing edges 2, set the budget B = n, and read a cheap tour back as a Hamiltonian cycle.

Guided construction

Hamiltonian Cycle → TSP

Step 1 of 6
Hamiltonian Cycle to TSP on five verticesA pentagon of five original cost-1 edges is completed by a pentagram of five cost-2 chords; the pentagon itself is a tour of cost five, exactly the budget B = n = 5.Source G — 5 vertices, 5 edges12345
Original edge of G — cost 1
Study next
Practise it

Add the markers S+T and 2S−T so an equal split of the new total 4S must separate them and expose a subset of sum T.

Guided construction

Subset Sum → Partition

Step 1 of 6
A = {3, 5, 6, 11}T = 14
Subset Sum to Partition via two added markersBars proportional to 3, 5, 6, 11 and to the markers 39 and 36 fill two pans that each total 50.Numbers drawn to scale35611
Original number
Study next
Practise it

Check reduction direction and follow hardness through a chain of canonical problems.

Guided construction

NP-complete reduction chain

Step 1 of 5
Known-hard Asource instance x
f(x)total polynomial compiler
Target B solverhypothetical fast algorithm
The solver's yes/no answer decides A
Study next
Practise it

Explore the course reduction network and the transformation carried by every edge.

Guided construction

Canonical reduction map

Step 1 of 6
Canonical NP-complete reduction networkSAT flows to 3SAT, then branches into compatibility graphs, route problems, cut and coloring problems, and arithmetic encodings. Every edge names its concrete transformation.Tseitin + clause splittingSAT3SAT
Logic / compatibility
Visible branch: Logic source1 labeled transformations

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Study next

Turn a bounded computation into Boolean constraints using local tableau windows.

Guided construction

Cook–Levin tableau

Step 1 of 7
Input x = 10 · time bound T = 3 · tableau width S = 5
t=0
⊢
[q0,1]
0
□
□
Study next
Practise it

Encode variable choices and clause satisfaction in no-carry digit columns.

Guided construction

3SAT → Subset Sum

Step 1 of 6
φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂)
number
x₁
x₂
C₁
C₂

The pages this was written from

2 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Study next

Walk the construction and both directions of the proof.

Guided construction

3NAE → 3-Colouring

Step 1 of 7
Input φ(x ∨ y ∨ z) ∧ (¬x ∨ y ∨ ¬z)
3NAE to 3-colouring: N, literal vertices and clause trianglesA special vertex N is joined by black edges to six literal vertices; blue edges join each literal to its negation; each of the two clauses owns a red triangle whose vertices are linked to the literals of that clause.NN — burns colour 1x¬xy¬yz¬zliteral vertices — 2n = 61:x1:y1:z2:¬x2:y2:¬zC₁ = (x ∨ y ∨ z)C₂ = (¬x ∨ y ∨ ¬z)clause vertices — 3m = 6

Walk the construction and both directions of the proof.

Guided construction

3-Colouring → 4-Colouring

Step 1 of 7
3-colouring to 4-colouring: adding one universally joined vertexThe left panel shows the input graph with a colouring; the right panel shows the same graph plus a new vertex joined to every original vertex, with its colouring. Later steps swap the input for K₄ and compare the identity map, an isolated extra vertex and the real construction.Input instance of 3COLG = C₅v₁1v₂2v₃1v₄2v₅3C₅ ∈ 3COL ✓
edge of G (kept)colour 1 (dashed)colour 2 (solid)colour 3 (dotted)

Walk the construction and both directions of the proof.

Guided construction

Vertex Cover → Dominating Set

Step 1 of 7
⟨G, k = 2⟩ ∈ VC ?
Vertex Cover to Dominating Set: an edge vertex for every edge, isolated vertices deletedThe source graph G with vertices a, b, c, d and an isolated vertex z sits on the left. On the right the graph Ĝ adds one vertex per edge joined to both endpoints, deletes z, and carries the same threshold k. Highlights show the cover U reused as a dominating set, a dominating set containing a new vertex, and the repair map that sends that new vertex back to an original one.G — the source graphabcdzisolated
original vertex of V

Walk the construction and both directions of the proof.

Guided construction

Vertex Cover → Subset Sum

Step 1 of 8
G = P₅: |V| = 5, m = |E| = 4K = 3
The input path beside a chart of the edge-column totalsOn the left a path of five vertices and four edges, each edge carrying a badge with how many of its endpoints were chosen. On the right one bar per edge column, split into the part contributed by chosen vertices and the part contributed by that edge's own number, against guide lines at the target 2, the maximum 3, and the carry threshold 10.G — the input graphEdge-column totals cⱼe₁e₂e₃e₄v₁v₂v₃v₄v₅02310e₁e₂e₃e₄
Vertex number a_v
One row per constructed number; one column for d and one for each edge; the last rows give the column totals and the target.
numberde₁e₂e₃e₄value
Step 0 — at most K becomes exactly KIf K > |V| replace K by |V|. A cover of size ≤ K always pads up to size exactly K, so forcing K in column d is harmless.

Walk the construction and both directions of the proof.

Guided construction

SAT → MaxIS

Step 1 of 7
φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃)m = 3 clauses
The graph G-phi built from a three-clause CNF formulaSeven vertices grouped in three clause columns. Solid red edges make each clause a clique; dashed dark edges join each literal to its negation. Three chosen vertices, one per clause, form an independent set of size three.G_φ — one vertex per literal occurrenceC₁ = (x₁ ∨ ¬x₂)C₂ = (¬x₁ ∨ x₂ ∨ x₃)C₃ = (¬x₂ ∨ ¬x₃)x₁¬x₂¬x₁x₂x₃¬x₂¬x₃¬x₂ occurs twice → two vertices
Vertex = one literal occurrence

Walk the construction and both directions of the proof.

Guided construction

co-IS → MaxIS

Step 1 of 7
⟨G, k⟩ = ⟨C₅, 4⟩co-IS: does G have no independent set of size 4?
Complement lemmaf reduces A to B ⇔ f reduces Ā to B̄ — so a reduction may start from co-IS.
A five-cycle with three planted vertices joined to every original vertexThe original graph is a pentagon of five vertices. Three planted vertices stand in a column to its right, with no edges among themselves and one thin edge to each of the five original vertices. In the comparison step the same graph is shown twice, once with those join edges and once without.G = C₅ — the input graphv₁v₂v₃v₄v₅α(G) = 2 ≤ k − 1 = 3, but not necessarily equal
Original vertex of VSolid: original edge of GIndependent set under discussion, ✓ ringed

Walk the construction and both directions of the proof.

Guided construction

Vertex Cover → 3-Uniform Hypergraph Cover

Step 1 of 7
⟨G, k = 2⟩ ∈ VC ?
Vertex Cover to 3-uniform hypergraph cover: each edge is inflated by a fresh vertexThe source graph G with vertices a, b, c, d and edges ab, ac, bc, cd is shown on one side. On the other side the hypergraph H keeps those four vertices, adds a square vertex for each edge, and draws every hyperedge as a shaded area covering exactly three vertices. Highlights show the cover U reused unchanged, a hypergraph cover that contains a new vertex, and the repair map trading that new vertex for one of its two real endpoints.G — the source graph (edges of size 2)abacbccdabcd
original vertex of V (circle)

Walk the construction and both directions of the proof.

Guided construction

Max-Cut on multigraphs → simple graphs

Step 1 of 7
|E| = 4k = 3
Max-Cut on a multigraph reduced to Max-Cut on a simple graphOn the left a multigraph with two parallel edges and a loop; on the right the simple graph in which every edge became a path of length three through two private vertices, with the cut sides, the crossing edges and the parity cases marked.G — multigraphe₁e₂e₃e₄abcG′ — simple graphV′ starts as V
original vertex of V

Walk the construction and both directions of the proof.

Guided construction

Vertex Cover → Modest Graph

Step 1 of 7
⟨G, k = 3⟩ ∈ VC ?modest ⇔ every degree ≤ 1
Vertex Cover to modest graph: a pendant leaf on every original vertexThe source graph G, a triangle a, b, c with a pendant vertex d on c, is shown on one side. On the other side the graph G prime hangs a small leaf vertex on each of a, b, c and d. Degree badges appear next to every surviving vertex, deleted vertices are struck through, and highlights show the cover U reused as a deletion set, a deletion set that wastes a unit on a leaf, and the repair map that swaps that leaf for the vertex it hangs from.G — the source graphabcd
original vertex of V (large circle)original edge of E

Walk the construction and both directions of the proof.

Guided construction

Directed → Undirected Hamiltonian Cycle

Step 1 of 7
Directed Hamiltonian Cycle reduced to Undirected Hamiltonian CycleOn the left a directed graph on four vertices; on the right each vertex is expanded into an in, mid and out vertex arranged around a circle, so that the Hamiltonian cycle runs along the ring and the degree-two middle vertices force a uniform direction.G — directed1→22→33→44→13→11234G′ — undirectedeach vertex is about to become a triple

Walk the construction and both directions of the proof.

Guided construction

3SAT → 4NAE

Step 1 of 7
φ = (x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₂ ∨ ¬x₃) ∧ (x₁ ∨ ¬x₂ ∨ ¬x₃)
3SAT to 4NAE: clause table with the appended literal zEach row is a clause and each cell a literal, coloured by its value under the current assignment. The fourth column holds the shared fresh literal z. Verdict pills on the right say whether the clause is satisfied and whether it is not-all-equal.φ under v = (1,1,1) — satisfied, but clause 1 is all-trueC₁x₁ = 1x₂ = 1x₃ = 1satisfied ✓all equal ✗C₂¬x₁ = 0x₂ = 1¬x₃ = 0satisfied ✓NAE ✓C₃x₁ = 1¬x₂ = 0¬x₃ = 0satisfied ✓NAE ✓x₁ = 1x₂ = 1x₃ = 1
literal value 1literal value 0

Walk the construction and both directions of the proof.

Guided construction

4NAE → 3NAE

Step 1 of 7
4NAE reduced to 3NAE by splitting every clauseTwo four-literal clauses are each split into two three-literal clauses joined by a fresh variable and its negation; literal values are shown as circles for true and squares for false, followed by the three forward cases and the backward extraction of a true and a false literal.φ — 4CNF, read under NAEC₁xℓ₁yℓ₂zℓ₃¬wℓ₄C₂¬xℓ₁wℓ₂zℓ₃yℓ₄each clause is about to be split in twoeach clause is about to be split in two

Walk the construction and both directions of the proof.

Guided construction

3SAT → exactly-3SAT

Step 1 of 7
v: x₁ = F, x₂ = F, x₃ = T
Padding short clauses up to exactly three literalsThe three input clauses of lengths three, two and one are mapped to seven output clauses: the full clause is copied, the two-literal clause becomes two clauses using a fresh variable, and the unit clause becomes four clauses using two fresh variables.φ — input, at most 3 literalsf(φ) — output, exactly 3 literalsbuilt clause by clause|C₁| = 3 · keepC₁x₁∨¬x₂∨x₃|C₂| = 2 · pad with y₂C₂¬x₁∨x₂|C₃| = 1 · pad with y₃, y₃′C₃x₃
Literal of φ

Complexity classes and space

6 visualizations

Distinguish proven containments and separations from open class equalities.

Guided construction

Complexity class containments

Step 1 of 4
Pdeterministic polynomial time
Proven containment
Study next

Build the quantifier levels of PH and examine the conditional collapse theorem.

Guided construction

Polynomial hierarchy lattice

Step 1 of 6
Σ₀ᴾ = Π₀ᴾ = Ppolynomial-time predicate
Begins existentiallyBegins universally
Study next
Practise it

Split reachability through midpoints while reusing workspace between recursive calls.

Guided construction

Savitch recursion

Step 1 of 6
Savitch configuration graph and recursionThe graph 1 to 2 to 3 with an extra edge from 1 to 4 is coordinated with a depth-first recursion for REACH of 1, 3, and level 2.Implicit configuration graph1234witness path: 1 → 2 → 3 (2 ≤ 4)Depth-first recursionbounded call appears next
Witness pathActive stack frame
Study next
Practise it

Relate original and padded input lengths without changing the underlying language.

Guided construction

Padding argument

Step 1 of 6
source xx = 101
101
n = |x| = 3
Meaningful instance xPadding suffix
Study next
Practise it

Clock a universal simulation, flip the answer on the diagonal, and separate DTIME(n²) from DTIME(n³) through the t·log t overhead.

Guided construction

Time hierarchy diagonalization

Step 1 of 6
simulated bound t₁(n) = n²diagonal machine bound t₂(n) = n³
Padding makes every machine recur

the same machine owns arbitrarily long inputs, so the clock eventually has room

⟨M₃⟩10⁰⟨M₃⟩10¹⟨M₃⟩10²⟨M₃⟩10³…
Time hierarchy diagonalization tableRows M₁ to M₅ against padded self-referential inputs w₁ to w₅, a clock budget of n² steps per column, the diagonal cells flipped into the row of D, and a disagreement marker under every column.machine ╲ inputw₁⟨M₁⟩10ᵏw₂⟨M₂⟩10ᵏw₃⟨M₃⟩10ᵏw₄⟨M₄⟩10ᵏw₅⟨M₅⟩10ᵏM₁·not run yet·not run yet·not run yet·not run yet·not run yetM₂·not run yet·not run yet·not run yet·not run yet·not run yetM₃·not run yet·not run yet·not run yet·not run yet·not run yetM₄·not run yet·not run yet·not run yet·not run yet·not run yetM₅·not run yet·not run yet·not run yet·not run yet·not run yet
not run yet

The pages this was written from

2 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Study next
Practise it

Give every machine the same oracle, compare the world where P^A = NP^A with the world where P^B ≠ NP^B, and see what a relativizing proof can never settle.

Guided construction

Relativization barrier

Step 1 of 6
Two oracle worlds sharing one machineOne oracle machine feeds the same relativizing chain P^O ⊆ NP^O ⊆ PSPACE^O into world A, where the classes are equal, and world B, where they are separated.Oracle machine — the same machine in both worldsMwork tapewrite qquery tapeone steporacle Oq ∈ Oq ∉ OWriting q still costs time, so queries stay polynomially long.
Shared structure — true for every oracle

The pages this was written from

2 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Study next
Practise it

Algorithms and approximation

8 visualizations

Fill and backtrack a pseudo-polynomial dynamic-programming table.

Guided construction

Subset Sum dynamic programming

Step 1 of 6
A = {3, 5, 6, 11} · target T = 14
i / sum
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0 items
✓
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Study next
Practise it

Contract random edges, preserve parallel edges, and expose the final cut.

Guided construction

Karger contraction

Step 1 of 6
Karger contraction on a square with one diagonalA protected two-edge minimum cut at B survives contractions of the diagonal A C and then a safe edge to D. Parallel edges are retained and a self-loop is deleted.ABCDprotected cut F at B, λ=2
Fixed cut used only in analysisContracted safe edge
Study next
Practise it

Repeat an RP run and take an OR, repeat a BPP run and take a majority, and watch the error fall exponentially in the number of independent trials.

Guided construction

Randomized error amplification

Step 1 of 6
Randomized error amplification across independent runsA strip of independent trials feeds an OR gate for RP and a majority gate for BPP, above a logarithmic plot comparing the RP error two to the minus k, the exact BPP majority error, the Hoeffding ceiling e to the minus k over eighteen, and a flat line for reusing the same random string.Independent runs (fixed illustration)RP · OR✗BPP · majority✓Error probability against the number of runs110⁻¹10⁻²10⁻³10⁻⁴10⁻⁵10⁻⁶10⁻⁷159131721k independent runserror probability (log scale)
✓ Run accepts a yes-instance · Run answers correctly✗ Run misses a yes-instance · Run answers wrongly
One run of eachRP: Pr[accept | yes] ≥ 1/2, Pr[accept | no] = 0BPP: Pr[correct] ≥ 2/3 on every inputEvery displayed outcome is a fixed illustration, so the picture never changes between readers.

The pages this was written from

3 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Study next
Practise it

Bound the MST by the optimal tour, double it into an Euler circuit, and shortcut with the triangle inequality to stay within twice the optimum.

Guided construction

Metric TSP double-tree 2-approximation

Step 1 of 6
Metric TSP double-tree 2-approximation on five pointsA complete metric instance on five points becomes a minimum spanning tree, then a doubled multigraph, then an Euler circuit, and finally a shortcut Hamiltonian tour.Complete metric instance8151319871210117ABCDE
Metric edge with its cost
Triangle inequalityCosts: AB 8, AC 15, AD 13, AE 19, BC 8, BD 7, BE 12, CD 10, CE 11, DE 7Holds for all sixty ordered triples of distinct points

The pages this was written from

1 page

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Study next
Practise it

Turn a Partition instance into bins of capacity S/2, watch the optimum collapse to 2 or 3, and derive that no polynomial-time algorithm beats absolute ratio 3/2 unless P = NP.

Guided construction

Partition → Bin Packing and the 3/2 barrier

Step 1 of 6
A′ = {3, 5, 6, 11, 39, 36}S = 100
Partition mapped to bins of capacity S/2 with the 3/2 ratio rulerItem blocks drawn to scale fill capacity-50 bins flush for the yes-instance and leave shaded slack in three capacity-51 bins for the no-instance, beside a ratio ruler marked 1, 11/9, 3/2, 1.7 and 2.Items drawn to scale356113936
Item block, height proportional to its value

The pages this was written from

3 pages

These pages were chosen by word overlap between the text here and the page's transcription — nobody has verified them. Treat them as a lead to check, not a citation.

Study next
Practise it

Track correctly directed bounds for minimization and maximization algorithms.

Guided construction

Approximation-ratio proof bridges

Step 1 of 6
minimizationOPT ≤ A ≤ α·OPTControl an algorithmic upper bound using an OPT lower bound.
maximizationOPT/α ≤ A ≤ OPTControl an algorithmic lower bound using an OPT upper bound.
Lower bound used for minimizationUpper bound used for maximization
Study next

Walk the construction and both directions of the proof.

Guided construction

General TSP has no constant approximation

Step 1 of 7
n = |V| = 5 · α = 2 · α|V|+1 = 11 · threshold αn = 10
Two five-vertex graphs completed with huge weights, and the gap between the two possible optimaOn the left a Hamiltonian graph whose optimal tour costs five; on the right a non-Hamiltonian bowtie whose cheapest tour must buy an edge of weight eleven and costs fifteen. A shared axis shows the yes interval from five to ten, the accept threshold at ten, and the no interval from fifteen upward, with an empty band between them.G ∈ UHCbowtie + chord {2,4}12345G ∉ UHCbowtie: 3 is a cut vertex12345
Original edge, w = 1
Why a Hamiltonian cycle existsThe chord {2,4} closes the cycle 1→2→4→5→3→1, which visits every vertex exactly once using only edges of G.
Why none exists in the bowtieDeleting vertex 3 leaves the two components {1,2} and {4,5}. A Hamiltonian cycle would have to pass through 3 twice to visit both, which a cycle cannot do.

Walk the construction and both directions of the proof.

Guided construction

Bin packing: the 3/2 absolute barrier

Step 1 of 7
bᵢ = 2aᵢ/S · Σbᵢ = 2 · bᵢ ∈ (0,1] · capacity 1
Two normalized bin-packing instances totalling two, and the integer axis on which the optimum is either two or threeOn the left a yes-instance whose six items split into two bins filled exactly to capacity one; on the right a no-instance needing three bins with visible slack. Below, an axis marked only at whole numbers shows the optimum at two or three, the empty band between them, and the value 2 rho equal to 2.98 collapsing down to 2.Normalized items, bᵢ = 2aᵢ/S, total 20.060.100.120.220.780.72A ∈ PARTITIONA = {3, 5, 6, 11, 39, 36}, S = 100capacity = 10.060.080.120.240.780.72A″ ∉ PARTITIONA″ = {3, 4, 6, 12, 39, 36}, S = 100capacity = 1
Normalized item bᵢBin capacity 1