So far, we have (mostly) been looking at problems for which we know efficient algorithms that solve them exist. However, we've stumbled across some problems for which we don't know whether there are efficient algorithms that solve them. This leads to the question of why we don't know whether they have efficient algorithms and whether we should expect to be able to come up with them.
These questions are far more relevant than they might seem. If we can't know whether or not there is an efficient algorithm, should we keep on trying to find one? Or is it a waste of time? How can we tell when we're presented with a problem that is difficult in this sense? Maybe these problems are rare or not that useful? Or maybe we're just not trying hard enough?
The answers to these questions are not entirely obvious. After all, the entire discipline of computer science was born in the early 20th century out of the desire for mathematicians to (essentially) automate logic and theorem proving. One of the first models of computation, the Turing machine, was defined in order to show that this was not possible and that there were problems for which no algorithm to solve it exists. The nature of such problems are the subject of another course.
The questions we face are not quite as extreme, but they come from the same place. The existence of hard problems places a philosophical and practical limit on the power of computation. And that would be a reasonable conclusion, except that the state of our understanding of these problems is not even as clear as being able to say that these problems are definitely impossible to solve efficiently.
We will first explore the main mechanism by which we can determine how hard a problem is: reduction. Reductions formalize a way to compare the difficulty of one problem with another. The intuition behind this idea is this: I know that if I can solve problem $A$, then I can solve problem $B$, by transforming an instance of $B$ into an instance of $A$. So if I have an efficient way to solve $A$ and an efficient way to transform an instance of $B$ into an instance of $A$, then I can efficiently solve $B$. That means that $A$ should be at least as hard to solve as $B$.
Note that for this comparison, it doesn't actually matter if we have an efficient algorithm for solving $A$. We just know that if we can somehow solve $A$, then that gives us a baseline for how hard it would be to solve $B$. This would be just as true whether we knew how $A$ was solved or not. We could have a mysterious tungsten cube that magically solves it for that matter.
Let's formalize this notion.
An oracle for a problem $X$ is a computational device that, when given an instance of $X$ will solve it in a single computational step.
Here, an oracle is an all-powerful magical device that solves a particular problem for us in one step. Obviously, such devices don't actually exist, or else we could've skipped a lot of classes. Oracles are sort of like a thought experiment: if we could solve a particular problem efficiently, what else would that let us solve efficiently?
A problem $A$ is polynomial-time reducible to a problem $B$, denoted $A \leq_P B$, if an instance of $A$ can be solved by:
Reductions are a tool that have been used since the beginnings of computer science, before they made their way over to complexity theory. Reductions were first used as a way to show that certain problems were unsolvable. In other words, there are problems for which there is no algorithm that can solve it, which is much stronger than our interest in efficient alogorithms.
So how do we use reductions? The idea is that we get a schematic diagram that looks roughly like the following:
Here, the green box is our algorithm that transforms an instance $I$ of $A$ into an instance $I'$ of $B$. The mysterious blue box then solves $B$ on $I'$ for us for free.
One of the things this should make clear is that just because $A \leq_P B$, it doesn't mean that $B \leq_P A$. That is, reductions are not symmetric!
However, if we can prove such a relationship, we can prove some things if we know a few more things about the problems that we're relating. In particular, if we have an algorithm for one of the problems instead of a magical cube, we can say some more interesting things.
Let $A$ and $B$ be problems. If $A \leq_P B$, then
Suppose there is an algorithm that solves $B$ in polynomial time, say $O(p(n))$ for some polynomial $p$. Since $A \leq_P B$, there is an algorithm that transforms an instance of $A$ into an instance of $B$ in polynomial time, say $O(q(n))$ for some polynomial $q$. Then we have the following algorithm that solves $A$:
Suppose the size of $I$ is $n$. How big can $J$ be? Since the transformation algorithm runs in $O(q(n))$ time, in the worst case, $J$ can have size $O(q(n))$, since we need to write $J$. Then the running time for the entire algorithm is $O(p(q(n)))$, which is polynomial in $n$.
Now, suppose that $A$ cannot be solved in polynomial time. Assume for contradiction that $B$ can be solved in polynomial time. Then by our above argument, we have a polynomial time algorithm for $A$, which contradicts that $A$ cannot be solved in polynomial time. Therefore, $B$ cannot be solved in polynomial time.
The idea of transforming a problem into a problem we already know how to solve is already useful, but here, we note that (2) is the contrapositive of (1), and this is really the statement that we're interested in for this next part of the course. Suppose we have a problem that we are thinking about solving. How do we know if we can write an efficient algorithm that solves it? One way would be that it's possible and we find it and write it. But what if we can't? The next best thing may be to compare it against some other problem that we already know is hard.
Before getting into what constitutes a hard problem, we'll first dive into how to perform these transformations, because that's most of what we'll be asking you to do in this part of the course.
We will begin with some fundamental graph problems.
Let $G = (V,E)$ be an undirected graph. We say a set of vertices $S \subseteq V$ is independent if no two vertices in $S$ are joined by an edge.
Here, we have a graph with an independent set highlighted in cyan. This is an independent set because no two vertices in the set are adjacent to each other.
Such sets are called independent because they're mutually independent of whatever relationship is defined by the graph. For instance, if you think of this as a social network, it's a group of people who don't share any friends in common.
One thing we might notice is that there's actually a much easier independent set than the one we exhibited. The set $\emptyset$ is an independent set, since no two vertices in the set are joined by an edge. So obviously, the challenge is we'd like to find as large an independent set as possible. This leads to the following question.
The independent set problem is: Given an undirected graph $G$ and integer $k \geq 0$, does $G$ contain an independent set of size at least $k$?
This might seem like a strange formulation for a problem. We are typically interested in optimization problems, which ask for a solution that maximizes or minimizes some particular property. So the natural question for something like independent set would be to find the independent set of maximum size.
Instead, we have what is called the decision problem variant of the optimization problem. The issue here is that the solution to an optimization problem is a solution, which complicates things. However, the answer to a decision problem is a Yes or No. This formulation of the problem is more convenient when discussing reductions, since it is more convenient to map Yes/No answers onto other Yes/No answers.
A question that this raises is whether the two problems are actually equivalent. If they're not, then this entire exercise is kind of pointless. Luckily, we can show that solving a decision problem means we can solve the optimization problem and vice-versa. One direction is obvious: solving the optimization problem automatically gives us an answer for the decision problem for any $k$.
The other direction is less obvious, but doable. If we have something like a graph, then we can employ binary search to search for the largest $k$ for which the answer is Yes.
Now, let's consider a similar problem.
Let $G = (V,E)$ be an undirected graph. We say a set $C \subseteq V$ is a vertex cover if every edge $e \in E$ is incident to at least one vertex in $C$.
Here, we have a vertex cover with vertices highlighted in yellow. These form a vertex cover because every edge is incident to at least one vertex in the cover.
Vertex cover is an example of a class of problem called covering problems, which involve trying to choose a set of elements that cover some relationships across the entire set. For graphs, those relationships are edges.
Just like independent sets, there is a very easy vertex cover we can choose to ensure that we cover every edge: the set $V$ itself. Since every edge is incident to a vertex in $V$, it's a vertex cover. So the challenge here will be to to find as small a vertex cover as possible. This leads to the following question.
The vertex cover problem is: Given an undirected graph $G$ and integer $k \geq 0$, does $G$ contain a vertex cover of size at most $k$?
So we want to relate these two problems somehow. One of the things you might notice from our two examples, which exhibit a maximum independent set and minimal vertex cover on the same graph, is that the independent set and vertex cover happen to be complements of each other. We will prove and make use of this observation.
Independent Set $\leq_P$ Vertex Cover.
Suppose we can solve Vertex Cover. We will show how to solve Independent Set by using an algorithm for Vertex Cover. Let $G = (V,E)$ be an undirected graph. We will show that a set $S \subseteq V$ is an independent set if and only if $V - S$ is a vertex cover.
Suppose $S$ is an independent set and consider an edge $(u,v) \in E$. Since $S$ is independent, we must have at least one of the following:
In any of these scenarios, $V-S$ covers $(u,v)$. Since $(u,v)$ was arbitrary, $V-S$ is a vertex cover.
Now, suppose that $V-S$ is a vertex cover and consider an edge $(u,v) \in E$. Since $V-S$ is a vertex cover, we must have at least one of the following:
In any of these scenarios both $u$ and $v$ will not be in $S$, so $S$ is an independent set.
Now, note that if $|S| = k$, then $|V-S| = n-k$. Therefore, we can solve Independent Set by running an algorithm on $G$ and asking whether $G$ has a vertex cover of size $n-k$.
One important note is that it is necessary to show that our transformation satisfies an if and only if statement. In essence, to show that $A \leq_P B$, what we're trying to do is map "Yes"es of $A$ to "Yes"es of $B$ and "No"s of $A$ to "No"s of $B$.
So you might say, okay, it makes sense to reduce Independent Set to Vertex Cover because they're both very closely related problems. But what if we considered something that wasn't about graphs at all?
Here, we will need to recall some definitions from propositional logic.
A boolean variable is a variable that can be assigned a value from $\{0,1\}$ (or $\{T,F\}$). A literal is a boolean variable or its negation. A clause is a disjunction of literals. We say a boolean formula $\varphi$ is in conjunctive normal form (CNF) if $\varphi$ is a conjunction of clauses.
Consider the formula \[\varphi = (\neg x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee \neg x_2 \vee x_3) \wedge (\neg x_1 \vee x_2 \vee x_4).\] This formula is in conjunctive normal form and has
Recall that propositional formulas are logical statements that assert the truth of some statement. Usually this is mathematical in nature. We are interested in determining whether such a statement is ever true. In other words, is there a way for us to assign the variables in such a way that the formula becomes true? This is called the satisfiability problem.
The satisfiability (SAT) problem is: Given a propositional formula $\varphi$, does it have a satisfying truth assignment? The 3-SAT problem is: Given a propositional formula $\varphi$ in conjunctive normal form, where each clause contains exactly three literals, does it have a satisfying truth assignment?
Satisfiability is a basic problem in mathematical logic and has obvious applications in things like circuit design. However, as mentioned before, there are a number of mathematical statements that one can express in propositional logic, so being able to solve this would mean being able to determine the satisfiability of any statement that can be expressed as a propositional statement.
We will show something that is maybe a bit surprising.
3-SAT $\leq_P$ Independent Set.
Given an instance $\varphi$ of 3-SAT, where $\varphi$ has $k$ clauses, we will construct an instance $(G,k)$ of Independent set that has an independent set of size $k$ if and only if $\varphi$ is satisfiable.
Our construction is as follows. For each clause $C = x_i \vee x_j \vee x_k$ in $\varphi$, we construct a triangle. Then, we add an edge between each literal and its negations in the other clauses.
Consider the following graph, constructed by using the formula from Example 8.12. Note that each triangle corresponds to a clause and that the literals $x_1$ and $x_2$ have edges to their negations, $\neg x_1$ and $\neg x_2$.
We will show that $\varphi$ is satisfiable if and only if $G$ contains an independent set of size $k$, where $k$ is the number of clauses in $\varphi$.
First, suppose $\varphi$ is satisfiable and consider a satisfying assignment. This means that in every clause, at least one of the literals is true. Then we choose one of these literals from each clause and these form an independent set $S$.
To see that they do, it is clear that only one vertex can be chosen from each triangle. Then all that remains is that there are no edges joining two vertices in different triangles. But the only way this can happen is between two literals $x_i$ and $\neg x_i$, which can't be the case in a satisfying assignment. therefore, $S$ is an independent set.
Next, suppose that $G$ contains an independent set $S$ of size $k$. Since $S$ is independent, it must contain exactly one vertex from each triangle. We set the literals corresponding to these vertices to True, as long as they are consistent. Then this means every clause evaluates to true, so $\varphi$ is satisfied.
In other words, we've shown that if we can solve this problem on graphs, then we can solve a totally different problem in logic. But doing a bit of thinking, we realize that this also gives us a way to transform 3-SAT into Vertex cover! It turns out that reduction is transitive.
If $A \leq_P B$ and $B \leq_P C$, then $A \leq_P C$.
With that we have the following relationships among the problems we've discussed so far: \[\mathrm{3SAT} \leq_P \mathrm{Independent\ Set} \leq_P \mathrm{Vertex\ Cover}.\]
Now, you might say that this seems like cheating: after all, we've just shown that a special version of boolean satisfiability can be turned into a graph problem. So to answer that question, we'll show that any boolean formula $\phi$ can be transformed into an equivalent formula in 3CNF.
Satisfiability $\leq_P$ 3-SAT.
We need to transform an arbitrary boolean formula $\varphi$ into one that is in CNF and has at most three literals per clause. To do this, we will go through a series of transformations, each of which preserves the truth of the original formula.
First, we will parenthesize the formula into what is sometimes called a well-formed formula. Essentially, this means rewriting the formula so that the order of operations are explicitly defined by the parentheses. It is clear that this rewriting doesn't change the formula.
Once we have such a formula, we can very easily construct a parse tree for the formula. For example, for the formula $\varphi = (((x_1 \to x_2) \wedge (x_3 \wedge \neg x_1)) \vee (x_2 \to \neg x_4)) \vee x_3$, we have the following parse tree.
We observe that in such a tree, the leaves are all literals and the internal nodes of the tree are all connectives. We observe that every connective has exactly two children. What we will do is, for each connective $(x \circ y)$, construct a clause $(z \leftrightarrow x \circ y)$, where $z$ is a new variable and replace the subformula with $z$. Since all connectives are binary, we have a set of clauses with three literals of the form $(z \leftrightarrow x \circ y)$.
For each of these clauses, we can rewrite them using only $\vee$ and $\wedge$ by using a truth table and writing the result in disjunctive normal form (ors of ands). Since all of our clauses are of the form $C = (z \leftrightarrow (x \circ y))$, we have a truth table
| $x$ | $y$ | $z$ | $C$ |
|---|---|---|---|
| T | T | T | ? |
| T | T | F | ? |
| T | F | T | ? |
| T | F | F | ? |
| F | T | T | ? |
| F | T | F | ? |
| F | F | T | ? |
| F | F | F | ? |
Then we can construct a formula in disjunctive normal form for $\neg C$ by taking each row that evaluates to $F$, $\wedge$ing the variables together and $\vee$ing those clauses.
For example, suppose $C = (z \leftrightarrow (x \wedge \neg y))$. Then
| $x$ | $y$ | $z$ | $(z \leftrightarrow (x \wedge y))$ |
|---|---|---|---|
| T | T | T | T |
| T | T | F | F |
| T | F | T | F |
| T | F | F | T |
| F | T | T | F |
| F | T | F | T |
| F | F | T | F |
| F | F | F | T |
This gives us the formula \[\neg C = (x \wedge y \wedge \neg z) \vee (x \wedge \neg y \wedge z) \vee (\neg x \wedge y \wedge z) \vee (\neg x \wedge \neg y \wedge z).\]
We then apply De Morgan's laws on our formula for $\neg C$ to turn the result into a formula for $C$ in conjunctive normal form. Again, this does not change the satisfiability of the formula.
This leaves us with clauses with three, two, or one literals. We can stuff the clauses with only one or two literals with dummy variables as follows:
where $p$ and $q$ are new variables. We use the same variables $p$ and $q$ for all clauses that need them. It is clear that adding these variables does not affect the satisfiability of the formula.
It remains to show that the construction can be done in polynomial time. It is clear that parenthesizing the formula can be done in one pass of the formula. Then what is the size of the parse tree? This looks like it could be exponential, but it's actually linear in the length of the formula: every node corresponds to either a literal or a connective in the formula. This is important, because we use the parse tree as the basis of our transformation.
Roughly speaking, we define a clause for each connective in our parse tree. This corresponds to one clause per internal node of the parse tree, which is linear in the length of the formula. Each clause increases the size of the instance by a constant amount. Then rewriting each clause also requires a constant amount of time and space: in the very worst case, we get a formula of eight clauses in DNF per clause we start out with.
In total, performing this transformation only increases the size of the formula linearly in the length of the original formula.
Now, we'll prove something about a simple, but important graph problem. The following notion was due to the Irish mathematician William Rowan Hamilton in the early 1800s.
Let $G$ be a graph. A cycle is a Hamiltonian cycle if every vertex of $G$ is in the cycle. A path is a Hamiltonian path if every vertex of $G$ is in the path.
The following graph contains a Hamiltonian cycle that is highlighted.
Hamiltonian cycles and paths have some very interesting applications. One is a connection to Gray codes, which are a binary code on $n$ digits that are defined such that the successor of a number only has a one digit difference from the current number.
The obvious question that we can ask about Hamiltonian cycles is whether our graph contains one.
The Hamiltonian Cycle problem is: Given a graph $G$, does $G$ contain a Hamiltonian cycle?
There is are directed and undirected flavours of this problem. Let's start with a simple reduction. We'll consider the undirected version, though it's not hard to show that the directed version reduces to the undirected one. Instead, we'll do something a bit more surprising: we'll show that 3-SAT reduces to Hamiltonian Cycle.
3-SAT $\leq_P$ Hamiltonian Cycle.
Let $\varphi$ be an instance of 3-SAT with $n$ variables and $k$ clauses. We will construct an instance of Hamiltonian Cycle. What we will do is try to construct a graph so that each possible assignment of variables corresponds to a Hamiltonian cycle. We then modify the graph by adding paths through clauses in such a way that we'll have a Hamiltonian cycle for those assignments that are satisfying.
The idea is that we need a way to tell whether we're setting a variable $x_i$ to True or False. So we create a series of vertices so that a path goes through the vertices from left to right if we set $x_i$ to True and we set it to False if the path goes the other way.
This gives us a way to define Hamiltonian paths through our graph that correspond to a particular assignment of variables. We then need to use this to indicate whether a clause has been satisfied by a particular assignment of variables it contains. We do this by hooking up vertices representing clauses to each of the paths for the corresponding variables.
If a literal $x_i$ is in a clause $C_j$, then the edges are such that $C_j$ is entered via the left from row $i$. Similarly, if the literal $\neg x_i$ is in a clause $C_k$, the edges are such that $C_k$ is entered via the right on row $i$.
These clause vertices are connected to the variable paths according to the literal. In order to space out these paths, we need $3k+3$ vertices in each variable path.
We need to argue that there is a satisfying assignment for $\varphi$ if and only if this graph $G$ we constructed has a Hamiltonian cycle.
Suppose $\varphi$ has a satisfying assignment. We can define our Hamiltonian cycle $\mathcal C$ by the following. If variable $x_i$ has been set to True, then the path moves through row $i$ from left to right; if $x_i$ is set to False, the path moves through row $i$ from right to left. Then for each clause $C_j$, there is at least one row for which the cycle can visit $C_j$. This only needs to happen once per clause, so the path only goes through $C_j$ once.
Now, suppose that $G$ has a Hamiltonian cycle. We need to recover an assignment for $\varphi$. For each row $i$, if the cycle goes from left to right, then $x_i$ is set to True; if it goes from right to left, we set $x_i$ to False. This assignment is satisfying because each clause vertex is visited by the Hamiltonian cycle. This vertex can only be visited by entering and exiting via vertices on the same row. This row corresponds to the literal that satisfies the clause. Since every clause is satisfied, $\varphi$ is satisfied.
It remains to show that this construction can be performed in polynomial time. We observe that the graph $G$ has $n(3k+3) + 2$ vertices, so the size of the graph is polynomial in the length of $\varphi$.
Here's a problem involving numbers, which will illustrate why we consider the size of numbers to be the number of their digits.
The Subset Sum problem is: Given a set of $n$ natural numbers $S = \{s_1, \dots, s_n\}$ and an integer $t \geq 0$, is there a subset $S'$ of $S$ such that the sum of elements of $S'$ is equal to $t$?
Consider the set $\{2, 45, 67, 84, 315, 346, 765, 1001\}$. If $t = 1192$, then a subset of numbers that adds up to $t$ is $\{45, 67, 315, 765\}$.
Where have we seen something like this before?
Subset Sum $\leq_P$ 0-1 Knapsack.
The reduction for this is pretty simple: Subset Sum is just Knapsack where the weight of each item is the same as its value. Then it's pretty clear that what you want to do is fill up your knapsack with items so that the weight of the items is as close to the weight limit $W$ as possible.
Is there something more exciting we can do with this problem? Yes! Let's relate it to one of the problems we've already seen. However, there doesn't seem to be a natural problem that we can construct a reduction from. However, we will show that we can get a reduction from 3-SAT.
3-SAT $\leq_P$ Subset Sum.
We will show how to transform an instance $\varphi$ of 3-SAT with $n$ variables and $k$ clauses into an instance $(S,t)$ of Subset Sum.
We will define $2n+2k$ integers, each with $n+k$ digits. This corresponds to two numbers per variable and two numbers per clause, where each digit corresponds to a variable or clause. For convention, we will use $n$ leftmost digits as digits for the variables and the $k$ rightmost digits as the digits for the clauses.
For each variable $x_i$, we construct the numbers $a_i$ and $a_i'$. For both numbers, the $i$th digit from the left is a 1. If $x_i$ is a literal in clause $j$, then the $n+j$th digit of $a_i$ is 1. If $\neg x_i$ is a literal in clause $j$, then the $n+j$th digit of $a_i'$ is 1. All other digits are 0.
For each clause $C_j$, we define the numbers $b_j$ and $b_j'$. The number $b_j$ has a 1 in the $n+j$th position and the number $b_j'$ has the number 2 in the $n+j$th position. All other digits are 0.
Then to define the target $t$, we define the number with 1 for every digit corresponding to a variable and a 4 for every digit corresponding to a clause.
For example, if we have $\varphi = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_3 \vee x_4) \wedge (x_1 \vee \neg x_2 \vee x_4)$, then we end up with the following numbers,
| $x_1$ | $x_2$ | $x_3$ | $x_4$ | $C_1$ | $C_2$ | $C_3$ | ||
|---|---|---|---|---|---|---|---|---|
| $a_1$ | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1000101 |
| $a_1'$ | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1000010 |
| $a_2$ | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 100100 |
| $a_2'$ | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 100001 |
| $a_3$ | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 10010 |
| $a_3'$ | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 10100 |
| $a_4$ | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1011 |
| $a_4'$ | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1000 |
| $b_1$ | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 100 |
| $b_1'$ | 0 | 0 | 0 | 0 | 2 | 0 | 0 | 200 |
| $b_2$ | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 10 |
| $b_2'$ | 0 | 0 | 0 | 0 | 0 | 2 | 0 | 20 |
| $b_3$ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
| $b_3'$ | 0 | 0 | 0 | 0 | 0 | 0 | 2 | 2 |
| $t$ | 1 | 1 | 1 | 1 | 4 | 4 | 4 | 1111444 |
One possible satisfying subset is highlighted.
We now need to show that we have a satisfying assignment for $\varphi$ if and only if there is a subset of these numbers that adds up to $t$.
Suppose we have a satisfying assignment. If $x_i$ is assigned to True, we add $a_i$ to our subset and if $a_i$ is assigned to False, we take $a_i'$. So each digit corresponding to $x_i$ sums up to 1. Since $\varphi$ is satisfiable, every digit corresponding to $C_j$ has a sum of at least 1.
Since we need each digit corresponding to $C_j$ to add up to 4, we add $b_j$ or $b_j'$ depending on how many literals of $C_j$ were set to True. If three literals were set to True, then this means that the digit sums up to 3 and we choose $b_j$. If two literals were set to True, the digit sums to 2 and we choose $b_j'$. If one literal was set to True, we choose both $b_j$ and $b_j'$.
So our chosen numbers sum up to $t$.
Now, suppose we have a subset $S'$ of numbers that sum up to $t$. We observe that each digit corresponding to a variable is 1, so we can only have one of $a_i$ or $a_i'$. If we have $a_i$, then $x_i$ is True and if $a_i'$ is in our set, then $x_i$ is False.
We claim that this is a satisfying assignment. To see why, we note that each digit corresponding to a clause is 4. Since the sum of $b_i$ and $b_i'$ is 3, this means there must be at least one 1 among the $a_i$'s chosen, which corresponds to the literal which satisfies the clause. Since every clause is satisfied, the formula is satisfied.
Finally, we have to show that our reduction is within polynomial time. Note that we defined the reduction on a per-digit basis. This is because for numerical problems, the size of the instance is measured in the size of the binary representation of the numbers. Since we were careful to define the digits of the Subset Sum instance, the size of the instance is quadratic in the size of the length of $\varphi$.