3-SAT to Vector Subset Sum (Karp Reduction)

Definition

3-SAT to Vector Subset Sum

There is a polynomial-time many-one reduction

$$3\text{-}\mathrm{SAT}{\le }_m^p\mathrm{VECTOR}\mathrm{SUBSET}\mathrm{SUM}$$

from 3-SAT to Vector Subset Sum. For a formula with $n$ variables and $m$ clauses, the construction uses dimension $d=n+m$, $2n+2m$ indexed vectors with entries in $\{0,1\}$, and a target with entries in $\{1,3\}$.

Construction

Let $F={\bigwedge }_{j=1}^m{C}_j$ have clauses of size at most three. Remove repeated literals within each clause and delete tautological clauses containing both $x_i$ and $\neg x_i$. These operations preserve satisfiability. Write $n,m$ for the resulting numbers of variables and clauses. A formula with no variables can be evaluated directly and mapped to a fixed one-dimensional yes- or no-instance.

Give each constraint its own coordinate

Use the first $n$ coordinates for variables and the remaining $m$ for clauses:

$$\tau =(\underset{n\text{ variable coordinates}}{\underbrace{1,\dots ,1}},\underset{m\text{ clause coordinates}}{\underbrace{3,\dots ,3}}).$$

A variable coordinate will force exactly one truth choice. A clause coordinate will require at least one true literal, with limited fill-up capacity handling the remaining amount.

Unlike the scalar subset-sum encoding, coordinates are separate equations, not digit positions in one large integer. There are no carries between them.

Encode the two truth choices for each variable

Introduce indexed vectors $v_{i,T}$ and $v_{i,F}$ for each variable $x_i$. Both have a $1$ in variable coordinate $i$ and $0$ in all other variable coordinates. Their clause coordinates record the literals they make true:

$$\begin{array}{rlrl}(v_{i,T}{)}_h=(v_{i,F}{)}_h& =\{\begin{array}{ll}1& h=i,\\ 0& h\ne i,\end{array}& & 1\le h\le n,\\ (v_{i,T}{)}_{n+j}& =1[x_i\in C_j],& & \\ (v_{i,F}{)}_{n+j}& =1[\neg x_i\in C_j],& & 1\le j\le m.\end{array}$$

Here $1[P]$ is $1$ if statement $P$ holds and $0$ otherwise. A literal’s membership in a clause records its occurrence, not its truth value.

In the highlighted row, setting $x_2$ false makes $\neg x_2$ true in $C_1$. For any selection with one truth vector per variable, the sum in clause coordinate $n+j$ is exactly the number $q_j$ of true literals in $C_j$.

Allow a satisfied clause to reach three, but not an unsatisfied one

For each clause $C_j$, add two distinct indexed copies

$$s_{j,1}=s_{j,2}=e_{n+j},$$

where $e_{n+j}$ has $1$ in coordinate $n+j$ and $0$ elsewhere. Each copy may be selected once. Thus their total contribution is $r_j\in \{0,1,2\}$, and the clause equation becomes
$q_j+r_j=3.$

The fill-up vectors cannot affect any variable coordinate or another clause. Output the indexed family of all truth and fill-up vectors, together with $\tau$. The vectors are indexed because even equal-valued copies must remain separately selectable.

Correctness

The target is reachable exactly when the formula is satisfiable

Forward: select a truth vector and then fill each clause

Let $\alpha$ satisfy $F$. Select $v_{i,T}$ if $\alpha (x_i)=\top$, and $v_{i,F}$ otherwise. This gives sum $1$ in each variable coordinate. In clause coordinate $n+j$, the contribution $q_j$ satisfies $1\le q_j\le 3$. Select $3-q_j$ of its two fill-up copies. This is possible since $0\le 3-q_j\le 2$, and the resulting coordinate sum is $3$. All coordinates equal $\tau$.

Backward: recover exactly one truth value per variable

Suppose a selection sums to $\tau$. Only $v_{i,T}$ and $v_{i,F}$ contribute to variable coordinate $i$, and both contribute $1$. Its target is $1$, so exactly one is selected. This defines a truth assignment $\alpha$.

For each clause, let $q_j$ be the contribution of selected truth vectors and $r_j$ the number of selected fill-up copies. Then

$$q_j+r_j=3,r_j\le 2,q_j=3-r_j\ge 1.$$

Therefore each clause has a true literal under $\alpha$. The assignment satisfies every clause, hence $F$.

Size and running time

The dimension and number of vectors are $d=n+m$ and $r=2n+2m$. An explicit dense representation contains

$$\underset{\text{vector entries}}{\underbrace{rd}}+\underset{\text{target entries}}{\underbrace{d}}=2(n+m{)}^2+(n+m)$$

entries. Each is a constant-sized integer. Initialising the arrays and recording literal incidences takes $O((n+m{)}^2)$ operations, so the reduction is polynomial. An empty clause has no truth-vector contribution and can receive at most $2$ from fill-up vectors, correctly preventing a solution.

Strong NP-hardness

Vector Subset Sum is strongly NP-hard

Vector Subset Sum is strongly NP-hard, even when every input-vector entry is $0$ or $1$ and every target entry is $1$ or $3$.

Proof

The reduction starts from NP-hard 3-SAT. Encoding every numerical entry in unary still uses constant space per entry, leaving a polynomial-sized output. The dimension also has polynomial magnitude. Thus the reduction remains polynomial under unary encoding. Hardness comes from the growing number of coordinates and selectable vectors, not from large numerical values.