Suppose we an instance of the 3-SAT problem given by with variables with and clauses for . Each clause can have at most 3 literals.
We will now construct an input to the subset-sum problem that will have input numbers and a target . We will want to talk about these numbers digits in base 10. i.e. express the number
then is its ‘th digit.
For each variable we will introduce two variables and . Let and . Then we define
For each we define two variables which are identical
Lastly we define our target
It is useful to talk about map where
This map is a bijection so it has well defined inverse
Observation
Let then
Any sum of the , , , and can have at most 5 in any digit (as each clause can have at most 3 literals and 2 values from the or ), therefore there is no overflow from one digit to another.
Any solution to the constructed subset-sum problem must have exactly one of or for each as has a 1 in its first digits. Therefore construct assignment for where
This takes to construct, as we just need to iterate through . So can be done in polynomial time.
Suppose we have a solution to the constructed subset-sum problem. Then we have a valid assignment by the observation.
When looking at the last digits of we require a 3 in each position. Therefore for each we have at least one such that therefore and we satisfy clause .
Therefore this is a valid solution to the 3-SAT problem .
Suppose we have a valid assignment to for the 3-SAT problem .
Then for each clause define to be the number of satisfied literals - note .
Now define
Consider the sum
For the first digits, as or we have .
For the last digits, we have and
which gives a 3 in these digits.