variable columns and clause columns, with slack digits

3SAT ≤p SUBSET-SUM

$\mathrm{3SAT}\le_p\mathrm{SUBSET\text{-}SUM}$ — the classical form of the reduction, encoding the choice of assignment and the satisfaction of clauses in carry-free digit columns.

The construction

On a 3CNF formula $\varphi$ with variables $x_1,\dots,x_n$ and clauses $C_1,\dots,C_m$ . All numbers are written in base $10$ with $n+m$ digits: $n$ variable columns followed by $m$ clause columns.

Two numbers per variable. For each $i$ $i$ define $y_i$ $y_{i}$ (for $x_i=\mathrm{True}$ $x_{i} = True$ ) and $z_i$ $z_{i}$ (for $x_i=\mathrm{False}$ $x_{i} = False$ ):
- in variable column $i$ — digit $1$ in both; in every other variable column — $0$ .
- in clause column $j$ — in $y_i$ , digit $1$ if the literal $x_i$ occurs in $C_j$ , else $0$ ; in $z_i$ , digit $1$ if $\overline{x_i}$ occurs in $C_j$ , else $0$ .
Two slack numbers per clause. For each $j$ define $g_j$ and $h_j$ , both with digit $1$ in clause column $j$ and $0$ everywhere else.
The target $S$ : digit $1$ in every variable column and digit $3$ in every clause column.
Return all the numbers together with $S$ .

What each column enforces. A variable column demands exactly $1$ , and only $y_i$ and $z_i$ carry a $1$ there — so exactly one of them is chosen, i.e. the assignment is well defined. A clause column demands $3$ , and the two slack numbers together supply at most $2$ ; so at least one variable number contributing to that column must be chosen — i.e. the clause is satisfied.

Visualization

φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂)

number

x₁

x₂

C₁

C₂

Correctness — both directions

3SAT ∈ ⟹ SUBSET-SUM ∈

Suppose $v$ satisfies $\varphi$ . Choose the numbers:

for each $i$ : if $v(x_i)=1$ take $y_i$ , otherwise $z_i$ .
for each $j$ : let $s_j\in\{1,2,3\}$ be the number of literals of $C_j$ that $v$ satisfies (at least $1$ , since $v$ satisfies $C_j$ , and at most $3$ ). Take $3-s_j$ of the slack numbers of $C_j$ — that is $2$ , $1$ , or $0$ of them. This is possible since $3-s_j\in\{0,1,2\}$ and there are two slack numbers.

Variable columns. In column $i$ exactly one number ( $y_i$ or $z_i$ ) contributed digit $1$ ; the slack numbers contribute $0$ there, and other variables' numbers contribute $0$ in column $i$ . The total is $1$ — as required.

Clause columns. In column $j$ the chosen variable numbers contribute exactly $s_j$ (the number of satisfied literals of $C_j$ ), and the chosen slack numbers contribute $3-s_j$ . The total is $s_j+(3-s_j)=3$ — as required.

Column totals are bounded: at most $2$ in a variable column and at most $3+2=5$ in a clause column, so nothing carries and digits may be read one by one. The overall sum is exactly $S$ .

SUBSET-SUM ∈ ⟹ 3SAT ∈

Suppose some subset $I$ sums to $S$ . Since every column total is bounded by $5<10$ (at most $2$ in a variable column; at most $3$ from variable numbers plus $2$ from slack in a clause column), nothing carries, so equal sums force equality column by column.

Variable columns. Column $i$ demands total $1$ . Only $y_i$ and $z_i$ carry a non-zero digit there, and both carry $1$ . So exactly one of them lies in $I$ . Define the assignment: $v(x_i)=1$ if $y_i\in I$ , and $v(x_i)=0$ if $z_i\in I$ . This is well defined and total.

Clause columns. Column $j$ demands total $3$ . The contributors are the slack numbers $g_j,h_j$ — at most $2$ together — and chosen variable numbers whose literal occurs in $C_j$ . So the variable numbers contribute at least $3-2=1$ , i.e. there exists a chosen variable number contributing $1$ to column $j$ .

Take such a number. If it is $y_i$ , then by construction the literal $x_i$ occurs in $C_j$ , and by definition $v(x_i)=1$ — the literal is satisfied. If it is $z_i$ , then $\overline{x_i}$ occurs in $C_j$ and $v(x_i)=0$ — again satisfied. Either way $C_j$ is satisfied.

As $j$ was arbitrary, $v$ satisfies $\varphi$ , i.e. $\varphi\in\mathrm{3SAT}$ .

Cost of the reduction

TimeO((n+m)²)

SpaceO((n+m)²)

Output size(2n + 2m + 1) numbers of n+m digits each

The output holds $2n$ numbers (two per variable) plus $2m$ (two per clause), each of $n+m$ digits. The total digit count is $(2n+2m)(n+m)+(n+m)=O((n+m)^2)$ — exactly the count the exam papers asked for. Time is proportional to output size.

As in $\mathrm{VC}\le_p\mathrm{SUBSET\text{-}SUM}$ : the value of each number is exponential in the input size while its written length is polynomial — and that is what makes the reduction legal.

What it buys

$\mathrm{SUBSET\text{-}SUM}$ is NP-hard, by a route that does not pass through $\mathrm{VC}$ .

Pitfalls

Two slack numbers per clause are needed, not one. A clause can be satisfied by $1$ , $2$ , or $3$ literals, so the shortfall to $3$ is $2$ , $1$ , or $0$ — and two slack numbers cover exactly those three cases. With one slack number, a clause satisfied by a single literal could not reach $3$ .
The clause-column target is $3$ , not $1$ . Were it $1$ , a slack number alone would satisfy the column with no variable number at all — and the backward direction would collapse.

The chain

Rests on

SAT ≤p 3SAT

Where this was read from

2025 '1 מועד 1"What is the total number of digits across all output numbers, for a 3CNF formula with $n$ variables and $m$ clauses?"
2024 '1 מועד 1"In class we saw a reduction from 3-SAT to Subset Sum" — tracing the match between a satisfying assignment and a subset.
2024 '1 מועד 2The same construction, on a concrete formula.
2023 '2 מועד 2A description of the reduction function into Subset-Sum, and whether it is legitimate.

An important mapping note: the 2026B lessons do not teach this reduction — lesson 11 proves $\mathrm{SUBSET\text{-}SUM}$ hard through $\mathrm{VC}$ , by a completely different construction (a column per edge). The 3SAT reduction is the one the 2023–2025 papers call "the one we saw in the lecture", i.e. it was taught in earlier years. Both constructions are correct and both are in the corpus; they must not be conflated — they differ in input, in columns, and in target.
Since this reduction has no lesson source in the corpus, the construction details above are the standard form consistent with what the papers do state (the digit count, the assignment↔subset correspondence). Minor differences of phrasing from the version given in class those years are possible.