The transformed instance here is not a graph, it is a list of integers, and the construction is a table of digits. The reason it works is arithmetical: the largest column total is 5 and the base is 10, so no column can carry into the next and the columns are independent. The lab adds every digit of every row to check that, and the same page explains why a problem with a table-filling algorithm is NP-hard anyway.
Core ideas
The first idea is that a number can be a data structure. The second is the arithmetical fact the whole construction rests on and that readers skip. The third is the distinction between a problem that is hard in the size of its input and one that is hard in the magnitude of its numbers.
Each variable gets a number for x true and a number for x false, each carrying a 1 in its own variable column and a 1 in every clause column the literal satisfies. The target has 1 in each variable column, which forces exactly one of each pair into the subset, and 4 in each clause column. So choosing a subset that hits the target is choosing an assignment, and the arithmetic does the work the triangles did in the graph construction.
The construction is nonsense if a column can carry, because then a shortfall in one column could be made up by an excess in another and the columns would stop encoding independent constraints. The panel adds every digit of every row, whether the row is in the subset or not: a variable column totals 2 and a clause column totals at most 6 — three literal occurrences plus the slack numbers 1 and 2. Six is less than ten. On the loaded formula the largest total is 5 and the panel prints it against the base.
Subset sum has a dynamic programme filling a table of size proportional to the number of items times the target, which Dynamic Programming and Optimal Substructure built. That is polynomial in the target's value and exponential in its number of digits, and the input is the digits. Here the target has one digit per variable plus one per clause, so the numbers this reduction produces are astronomically large in the formula's size and the table is no help. A problem hard only when its numbers are large is weakly NP-hard, and subset sum is the standard example.
The material
The construction, the target, the column totals the lab adds, the bijection on solutions, and the two senses in which a problem can be hard.
Given a list of positive integers and a target, is there a sublist adding to the target exactly? The input is the digits of the numbers, which matters for every complexity claim on this page: a list of ten numbers with a thousand digits each is a large input, and a list of ten numbers under 100 is a small one.
The formula is satisfiable if and only if some subset of the constructed numbers adds to the target.
No column can carry, because every column's digits add to at most 6 across all the rows, and 6 is less than 10. So a subset hits the target exactly when it hits each column's digit separately.
A variable column can only be reached by that variable's two numbers, each contributing 1, and the target is 1, so exactly one of the two is chosen: the subset picks an assignment. A clause column receives 1 from each chosen literal number that satisfies the clause, so between 0 and 3, plus whatever the two slack numbers contribute, which is 0, 1, 2 or 3.
The target is 4. If the assignment satisfies the clause, the literal contribution is 1, 2 or 3 and exactly one of the four slack combinations makes up the remaining 3, 2 or 1. If the assignment does not satisfy it, the literal contribution is 0 and the slack numbers can supply at most 3, so the column cannot reach 4. Hence the subsets that hit the target are exactly the satisfying assignments, each with its forced slack choice — which is why the map is not merely sound but a bijection.
□
The loaded formula is (x1 or x2) and (not x1 or x2): two variables, two clauses, so four columns. The panel reports 8 numbers of 4 digits, the target 1144, 2 subsets reaching it, 2 satisfying assignments out of 4, a largest column total of 5 against the base 10, and the verdict that the map is a bijection — sound, surjective and injective, all three computed.
The column totals are 2, 2, 5 and 5. The two variable columns get a 1 from each of the variable's two numbers and nothing else. Each clause column gets a 1 from every literal number satisfying that clause — two of them here — plus 1 and 2 from the slack, which is 5. Five is comfortably under ten and the bar chart draws it against the line.
Beside the enumeration the panel runs the dynamic programme from Dynamic Programming and Optimal Substructure on the same numbers and the same target, and requires the two to agree about whether the target is reachable. Two exhaustive routes that agree is evidence; one clever route is not, and the two routes here share no code.
x1 false + x2 true + slack 1.1 + slack 1.2 + slack 2.2 is 1001 + 0111 + 0010 + 0020 + 0002 = 1144, and carries back to x1 = F, x2 = T. The clause-1 column reads 1 from x2 true plus 1 and 2 from the slacks; the clause-2 column reads 1 from x1 false, 1 from x2 true and 2 from a slack. Both reach 4 without help from anywhere else in the number.
It is tempting to think a problem with a dynamic programme cannot be NP-hard. The table for subset sum has one row per item and one column per value from 0 to the target, so its size is proportional to n times the target. That is polynomial in the target as a NUMBER and exponential in the target as an INPUT, because a target with d digits has magnitude about 10^d. Here d is the number of variables plus the number of clauses, so the table has about 10^(n+m) columns and is not an algorithm anyone can run.
The distinction has a name and a consequence. A problem that is NP-hard but has an algorithm polynomial in the numeric values is weakly NP-hard; one that stays hard even when the numbers are bounded by a polynomial in the input length is strongly NP-hard. Only weakly NP-hard problems can have the kind of approximation scheme built later on this course, and that is not a coincidence: the scheme works by making the numbers small enough for the table to fit.
Interactive
One column per variable and per clause, a target of 1s and 4s, and a base large enough that no column can carry
Method
The construction is four lines. The check that makes it valid is one addition per column, and it is the step to do first.
One per variable, one per clause. The number of columns fixes the width of every row and the magnitude of every number, and it is the quantity that makes this reduction produce astronomically large integers from a small formula.
Not over the rows in a solution — over all of them. The question is whether a carry is possible at all, which is a property of the table rather than of any subset. The panel prints the totals and colours the bar red if any total reaches the base.
The target digit is 1 and exactly two rows contribute to that column, so exactly one is chosen. If a construction lets both or neither be chosen it is not encoding an assignment, and no amount of correct clause arithmetic will repair it.
A satisfied clause receives 1, 2 or 3 from its literals and the slack numbers can supply 3, 2 or 1 in exactly one way each. An unsatisfied clause receives 0 and the slack tops out at 3. Both halves are needed: the first makes the map onto the models, the second makes it sound.
For any algorithm you quote on a numeric problem, name whether the bound is polynomial in the input length or in the magnitude of the numbers. The two coincide for graph problems and diverge here, and every confused claim about subset sum lives in that gap.
The formula is (x1 or x2) and (not x1 or x2). Columns left to right: x1, x2, clause 1, clause 2. A digit of 1 in a clause column means this literal satisfies that clause.
Both models have x2 true, and they must: if x2 were false the two clauses would read x1 and not x1. So the x2 true row is in both subsets and the x2 false row is in neither, which is the assignment being forced showing up as a row that is never chosen.
The slack choices are the part worth checking by hand. In the first subset clause 1 gets 1 from x2 true and needs 3 more, so both slacks are taken; clause 2 gets 1 from x1 false and 1 from x2 true and needs 2 more, so only the 2 is taken. Each shortfall has exactly one repair, which is the injectivity of the map made concrete.
For a faded rehearsal, switch to the single-clause example and predict the target before running it. The supplied first move: two variables and one clause means three columns, and the target is 1 in each variable column and 4 in the clause column. Say what the target is as a number and how many rows there are, then check — and note that being right about this table says nothing about the three-variable one, where the largest column total moves to 6.
You should be able to lay out the columns, write both numbers for each variable and both slack numbers for each clause, state the target, add each column over every row to show no carry is possible, and say whether a numeric algorithm you quote is polynomial in the input length or in the magnitude of the numbers.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.