Motivation
Subset sum asks whether some of a list of nonnegative integers add exactly to a target. Its simple arithmetic statement hides a combinatorial search over subsets. To prove hardness, we encode a Boolean assignment in selected numbers and use separate digit columns to check all clauses at once.
The construction depends on preventing carries between columns. Each column has a fixed target and a small maximum possible sum, so it can be reasoned about independently. We use the NP-completeness of 3-SAT as background; that theorem is imported here and not proved in this unit.
Definitions
Definition 4.4.1
(Subset-sum instance)
A subset-sum instance is a finite list of nonnegative integers and a nonnegative target, all encoded in binary. It is a yes-instance if some subset of list positions sums to the target. Equal numerical values in different positions are distinct choices.
Definition 4.4.2
(Decimal-column encoding of a 3-CNF formula)
A 3-CNF formula has an explicitly listed variable set and clauses , each containing exactly three literal occurrences; repeated occurrences are allowed. For every variable make two numbers, corresponding to true and false. Use decimal digit positions: one variable column per variable and one clause column per clause. Both numbers for variable have digit one in its own variable column and zero in other variable columns. In clause column , the true-choice number has as its digit the number of occurrences of in , and the false-choice number has the number of occurrences of in .
For every clause column add two slack numbers, with digits one and two in that column and zero elsewhere. The target has digit one in every variable column and digit four in every clause column. Decimal numbers are then converted to their binary encodings for the subset-sum instance.
Theorems
Theorem 4.4.3
(Correctness of the reduction)
The constructed subset-sum instance has a solution if and only if the input 3-CNF formula is satisfiable.
Theorem 4.4.4
(Subset-sum completeness)
Subset sum is NP-complete under polynomial-time many-one reductions, assuming the standard NP-completeness of 3-SAT.
Proof sketch or proof idea
Proof
(Column sums stay below ten, so digits decide the equality)
No column can produce a decimal carry, even if an arbitrary subset of all numbers is chosen. A variable column receives at most two, from its two choice numbers. A clause has three literal occurrences, so across all selected variable numbers its contribution is at most three; the two slack numbers add at most three. Its total is at most six. Thus equality to the target holds exactly when each column sum equals its target digit.
A variable column has target one, so exactly one of its two choice numbers is selected. Interpret those choices as a truth assignment. In each clause column the selected variable numbers contribute exactly the number of true literal occurrences. The slack numbers can add or , so the target four can be reached exactly when . It cannot be reached when . Therefore every subset-sum solution gives a satisfying assignment.
Conversely, choose the true- or false-choice number specified by a satisfying assignment. Every clause has true occurrences. Select slack numbers summing to , which is one of . All variable and clause columns match, so the chosen numbers sum to the target. Repeated literals are counted as occurrences, and the same reasoning still applies.
Proof X-ray
No carries make the columns independent
The bound that every column total is at most six is used twice. In the forward direction it lets us read the target integer digit by digit for an arbitrary subset, before anything is known about which numbers were chosen; this is what lets each variable column force exactly one choice. In the backward direction it guarantees that the assignment-shaped subset really sums to the target.
The non-obvious design choice is the slack pair with target digit four. Its subset sums are exactly the complements needed for true occurrences and fall short for . Changing the base or the target digit would require rechecking both this separation and the carry bound; without the bound, a carry could make an apparent digit match hide a different selection.
Proof
(Polynomial size and membership in NP)
The output has numbers with decimal digits each, so their binary lengths and construction time are polynomial in the explicit formula size. A subset is a polynomial-length certificate, and binary addition verifies its sum in polynomial time. Thus subset sum is in NP; the reduction from NP-complete 3-SAT proves NP-hardness. The empty formula is satisfiable and maps to the target-zero instance with no numbers. Malformed input encodings can be mapped to a fixed no-instance, making the reduction total.
Worked examples
Worked example 4.4.5
(One repeated-literal clause)
For , use two columns: variable then clause. The true and false numbers are and ; slack numbers are and ; the target is . Choosing true gives . Choosing false leaves clause contribution zero, and both slack numbers give only three, so the target cannot be reached.
Worked example 4.4.6
(A satisfied clause with two true occurrences)
If the chosen variable numbers contribute in a clause column, select the slack number with digit two. The resulting column sum is four. The slack choice adjusts a satisfied clause but cannot repair a clause with zero true occurrences.
Worked example 4.4.7
(A clause with three true occurrences)
If all three occurrences are true, the variable contribution is three and the slack number with digit one reaches the target four. The maximum possible contribution after both slack numbers is six, still below the decimal base.
Common mistakes
Counterexample mode
A target without slack can reject a satisfied clause
If the clause target were four but no slack numbers were supplied, a clause with exactly one true literal would contribute only one and fail the digit test despite being satisfied. Slack represents the possible differences for .
Common mistake
(Selecting numbers without the one-choice constraint)
The variable-column constraint enforces exactly one choice per variable; merely selecting some true-looking numbers is not enough. Selecting neither number of a variable leaves its column at zero instead of one, and selecting both makes it two.
Common mistake
(Checking only assignment-shaped subsets)
The converse proof must treat an arbitrary subset-sum solution, not only subsets built from assignments, and this needs the no-carry bound for every subset. The clause columns also count literal occurrences, repetitions included.
Building the numbers column by column
The digit positions are conceptual labels; a fixed order of variable columns followed by clause columns gives an ordinary decimal integer. Leading zeros are allowed in the display but do not change its numerical value. The two slack numbers for a clause have zeros in every other column, so they affect only that clause's total. The two choices for a variable agree in the variable column but differ according to which literals they make true.
For example, if a clause contains two positive occurrences of and one occurrence of another variable, the true-choice number for has digit two in that clause column, and its false-choice number has digit zero there. If a clause contains both and , the true and false numbers record their respective occurrences. Choosing exactly one number for ensures that each occurrence contributes one precisely when that literal is true.
Worked example 4.4.8
(Two clauses and two variables)
Let and . Write columns in the order . The choice numbers are and for true and false, and and for true and false. The target is . Choosing gives ; adding slack digits two in each clause column gives . If is true and false, the selected choices give ; the second clause column is zero and cannot reach four using slack worth at most three.
The order of decimal columns is arbitrary as long as every number and the target use the same order. Converting the constructed numbers to binary changes their representation, not their values or the subset-sum equality. An explicit variable list ensures that and are bounded by the length of the formula representation; unused listed variables still receive a choice column.
Why the no-carry argument covers every subset
The reverse implication must analyze an arbitrary subset-sum solution, not just subsets built from assignments. Before we know that exactly one choice number per variable is selected, both might be selected or neither might be selected. Even then, a variable column receives at most two. In a clause column, each literal occurrence appears in exactly one of its variable's true- or false-choice numbers. Selecting all choice numbers therefore contributes at most the clause's three occurrences. Slack adds at most , so every clause total is at most six.
All digits and numbers are nonnegative. Since every raw column total is below ten, ordinary base-ten addition produces no carry from any column. Thus a sum equals the target integer if and only if all its column totals equal their target digits. This statement is what allows the variable columns to force one choice and the clause columns to enforce satisfaction. Bounding only the sums for assignment-shaped subsets would leave a gap in the converse proof.
Concept lensAlgebraic
One integer equation as one equation per column
Because no column carries, the instance is equivalent to a system of linear equations in unknowns, one per column. Variable column reads . Clause column reads , where is the total of occurrences of in the selected choice numbers and select the two slack numbers. The decimal digits merely pack all these equations into a single integer equation.
The target digit four is chosen to separate zero true occurrences from one, two or three. The slack sums form . For , the needed complements are respectively. For , the needed complement is four and is unavailable. The exact numbers are not sacred, but a different base or target would require rechecking both this separation and the carry bound.
Reduction direction and certificates
The mapping takes a formula as input and produces a subset-sum instance. A hypothetical polynomial-time subset-sum decider would therefore decide 3-SAT by first applying the mapping. This is the direction needed to transfer NP-hardness from 3-SAT to subset sum. A mapping in the opposite direction would not, by itself, prove subset sum hard.
The two solution transformations are explicit. A satisfying assignment chooses one number per variable and the appropriate slack positions. A subset summing to the target chooses exactly one number per variable; those choices determine a satisfying assignment. This is equisatisfiability, not a promise that every formula assignment corresponds to exactly one subset under every possible encoding convention. For example, distinct list positions with equal numerical values remain distinct subset choices.
For NP membership, a certificate can be a bit vector indicating which list positions are selected. Its length is the number of input integers. A verifier adds the selected binary integers and compares the result with the binary target using polynomial-time integer arithmetic. The numeric values can be large even though their encodings are short; a time bound polynomial in the target value would be a different, pseudopolynomial statement.
Size and edge cases
Each constructed decimal number has at most digits. Its binary length is at most a constant times , because it is smaller than . There are numbers, and each digit can be computed by scanning the explicitly listed literal occurrences. The reduction therefore runs in polynomial time in the formula encoding. It does not enumerate all assignments.
The empty conjunction of clauses is true. With no variables and no clauses, the construction produces an empty list and target zero; the empty subset witnesses a yes-instance. With variables but no clauses, each variable column requires one of the two choice numbers and the formula remains satisfiable. A formal total mapping should also define behavior on malformed encodings. Mapping each malformed string to a fixed subset-sum no-instance is one standard choice and does not affect the correctness proof for valid formulas.
The construction is deliberately tailored to clauses with exactly three occurrences. If a different input convention permits shorter clauses, first pad each nonempty clause by repeated occurrences or give a separate digit analysis. An empty clause is false and can be mapped directly to a fixed no-instance. These choices should be stated rather than assuming every 3-SAT convention is identical.
Summary
Variable columns force a truth choice, clause columns count true literal occurrences, and slack digits fill the target exactly when each clause is satisfied. The base-ten bound prevents carries and makes the column argument a valid integer-sum reduction.
Exercises
Quick check
(What are the possible sums of the two slack digits in one clause column?)
Consider each subset of the two slack numbers.
Solution · Answer
They are , from choosing no slack number, the one, the two, or both.
Quick check
(Why can a variable column never carry into a neighboring column?)
Count how many numbers have a nonzero digit in that column.
Solution · Answer
At most the two variable-choice numbers contribute one each, so the column sum is at most two, below ten.
Quick check
(If a clause has one true occurrence, which slack digits must be selected?)
The clause column must reach four.
Solution · Answer
Both slack numbers are selected, adding to the one true occurrence to reach four.
Quick check
(Why is the output length polynomial in the input length?)
Count the numbers and their digits.
Solution · Answer
There are numbers of decimal digits each; their binary encodings have polynomial total length.