Subset Sum and the Secret Language of Numbers

Overview

Kent Quanrud connects subset sum to the course’s earlier SAT reductions, showing how a 3-SAT instance can be encoded as positional digits in numbers so that a target-sum solution corresponds exactly to a satisfying assignment. He also explains why the natural dynamic program takes O(nT) time—polynomial in the target’s value but not necessarily its bit-length—and uses this reduction to show that subset sum is NP-hard.

Key takeaways

The natural subset-sum dynamic program runs in O(nT), but because T requires only log T bits to encode, this is pseudo-polynomial and can be exponential in the input length.
A positional digit can act as a separate constraint counter: variable positions enforce one truth choice, while clause positions count selected literals that satisfy each clause.
Adding two optional 1-contributions per clause converts the requirement that a clause receive at least one satisfying literal into an exact target of 3: totals 1, 2, and 3 can be padded to 3, while 0 cannot.
The 3-SAT-to-subset-sum construction has polynomial size, so a polynomial-time algorithm for subset sum would provide a polynomial-time algorithm for 3-SAT.
A decision oracle can often be turned into a solution-producing procedure by fixing choices one at a time and querying whether a valid completion still exists.

Chapters

0:00 From SAT and 2-SAT to the Theme of Hardness Reductions

Earlier lectures connected Boolean formulas, 3-SAT, and circuit satisfiability through polynomial-time reductions.
2-SAT has a linear-time algorithm based on implication graphs and reachability, while Max-2-SAT is hard because maximizing satisfied clauses allows a reduction from 3-SAT.
The recurring lesson is that problems with very different appearances can be equivalent in computational difficulty.

6:00 From Making Change to the Subset Sum Decision Problem

The coin-change example uses U.S. quarters, dimes, nickels, and pennies to introduce representing a target value as a sum.
Subset sum asks whether some subset of given numbers adds exactly to a target, with each input number usable at most once.
For the example target 52, the class identifies 14 + 18 + 10 + 10 as a valid subset.

9:30 Why Subset Sum Looks Searchable but May Still Be Hard

A proposed subset-sum solution is easy to verify by adding its numbers and checking whether the total equals the target.
The class considers whether sorting or a recursive strategy might yield an efficient algorithm, while noting that trying every inclusion/exclusion choice takes exponential time.
The discussion distinguishes having an algorithm from having one that runs in polynomial time.

12:09 The Include-or-Exclude Recurrence for Subset Sum

The recursive approach makes one decision for the first number: include it and reduce the remaining target, or exclude it and keep the target unchanged.
Base cases return true when the remaining target is zero and false when no usable numbers remain or the target becomes impossible.
Without caching, the two recursive branches produce roughly 2^n work for n input numbers.

17:00 Dynamic Programming Gives O(nT), Not Polynomial Bit Complexity

Memoizing states indexed by the remaining numbers and target yields O(nT) time, where n is the number of inputs and T is the target value.
The target T is encoded using only log T bits, so T can be exponentially larger than its representation length.
The algorithm is therefore pseudo-polynomial rather than polynomial in the total input size; it is useful when T is small, but not a general polynomial-time solution.

19:00 The Reduction Idea: Hide Boolean Constraints Inside Numbers

Quanrud proposes reducing 3-SAT to subset sum so a subset-sum solver could answer whether the original formula is satisfiable.
The key observation is that numbers are represented by positional digits, and each digit can record information about a variable or clause.
Adding selected numbers can combine those recorded values, turning Boolean requirements into conditions on the resulting sum.

23:00 Representing Truth Assignments as Selected Literals

The construction begins with one positive and one negative literal for each Boolean variable, such as x_j and not-x_j.
A valid selection must choose exactly one of those two literals per variable, encoding a truth assignment without contradictions.
It must also select a literal that satisfies each clause, such as choosing x_1, not-x_2, or x_3 for the clause x_1 OR not-x_2 OR x_3.

31:00 Literal Numbers Encode Variables and Clause Membership

Each literal becomes a positional number with a variable digit marking which variable it represents and clause digits marking the clauses in which it appears.
The positive and negative literal numbers for the same variable share the variable marker but differ in their clause-membership digits.
Selecting literal numbers and adding them makes each variable digit count the chosen truth value and each clause digit count selected satisfying literals.

38:00 Padding Numbers Turn Clause Satisfaction into Exact Equality

The variable digits must equal 1, enforcing exactly one selected literal for every variable.
A clause digit must be at least 1 to indicate that the clause is satisfied, but subset sum checks exact equality rather than an at-least condition.
Two extra padding numbers per clause, each contributing 1 to that clause digit, let totals of 1 or 2 reach the target 3; a total of 0 can reach only 2 and remains invalid.

50:00 The Target Sum Captures the 3-SAT Requirements

The target has a 1 in every variable position and a 3 in every clause position.
Matching the variable positions enforces one truth choice per variable, while matching each clause position requires at least one satisfying literal plus appropriate padding.
The constructed instance has size polynomial in the original formula’s variables and clauses, so a polynomial-time subset-sum solver would yield a polynomial-time 3-SAT solver.

54:00 Recovering Assignments from Yes-or-No Solvers

A yes-or-no SAT solver can produce an actual assignment by fixing one variable, asking whether the restricted formula remains satisfiable, and reversing the choice if needed.
The same self-reduction idea applies to subset sum: repeatedly test whether a candidate number can be included while preserving a solution.
The lecture closes by emphasizing reductions as a way to recognize when a new-looking problem inherits the difficulty of SAT.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.