NP-Completeness

Introduction

So far, we have designed efficient algorithms for a wide range of problems. But not all problems are so accomodating. In this section, we examine a class of problems for which no polynomial time algorithm is known (and for which there is strong theoretical reason to believe none exists).

Definitions

We study NP-completeness in the setting of decision problems, or problems with a yes/no answer. This is not much of a restriction, since most optimization problems that we have previously studied have a natural decision version (e.g. "for a graph $G=(V,E)$, does there exist a traveling salesman tour of cost at most $k$?").

We say a (decision) problem $A$ is in NP if a proposed solution can be verified in polynomial time. More precisely, there exists a polynomial-time algorithm that, given an instance $x$ of $A$ and a certificate $c$, correctly determines whether $c$ proves that $x$ is a yes-instance of problem $A$. For example, a certificate (proposed solution) for a SAT instance is a truth assignment to its variables; we can check in polynomial time whether this assignment satisfies the SAT formula.

A polynomial reduction reduction from problem $A$ to problem $B$, written as $A \le_P B$, is a polynomial-time computable function $f$ such that for any instance $x$ of $A$, $x$ is a yes-instance of $A$ if and only if $f(x)$ is a yes-instance of $B$. Intuitively, this means $A$ is "no harder" than $B$; given an efficient algorithm for $B$, we obtain an efficient algorithm for $A$ by transforming instances via $f$ and running $B$'s algorithm on the result. Note the direction; $A \le_P B$ means $B$ is at least as hard as $A$, a fact we will use when proving NP-hardness.

We say a problem $B$ is NP-hard if $A \le_P B$ for every problem $A \in \mathrm{NP}$. Intuitively, $B$ is at least as hard as every problem in NP; solving $B$ efficiently would let us solve all of $NP$ efficiently.

We say $A$ is NP-Complete if and only if the following conditions are true:

• $A \in \mathrm{NP}$: there exists a verifier that can check proposed solutions to an instance $x$ of $A$ in polynomial time.
• $A$ is NP-hard. To show this, we produce a polynomial-time reduction $B \le_P A$ from some problem $B$ already known to be NP-hard. By transitivity of $\le_P$, since every problem in NP reduces to B (as B is NP-hard) and $B \le_P A$, every problem in NP also reduces to $A$; so $A$ is NP-hard.

General Framework

NP-completeness proofs are an important part of CS4820, and they are sure to show up on exams. If you want to show that some decision problem $A$ is NP-complete, the proof generally has 4 steps, as follows:

1. $A \in \mathrm{NP}$. Show that there is a polynomial-time verifier for $A$. It should take in an instance of the problem Foo and a certificate (possible solution) to that instance, answering 'yes' if certificate is a correct solution and 'no' otherwise. This is usually straightforward and should almost always be done first. Don't forget to argue why the verifier runs in polynomial time!
2. Reduce from some NP-complete problem $X$ to $A$ (i.e. showing $X \le_P A$). You should pick a known NP-complete problem $X$. Your goal is to solve $X$ using an algorithm that solves $A$. You should do this by "reducing" or translating an arbitrary instance of $X$ into an equivalent instance of $A$. This way, if you have an algorithm that solves $A$, you can solve $X$ by reducing the problem to $A$ and running the algorithm for $A$.
3. Show that the reduction takes polynomial time. Make sure you aren't creating exponentially many gadgets/nodes!
4. Show that your reduction is equivalent. In other words, $x$ is a yes-instance of $X$ iff $f(x)$ is a yes-instance of $A$ (where $f$ is our reduction function). This has two parts.

• $(\Rightarrow)$ If $x$ is a yes-instance of $X$, then $f(x)$ is a yes-instance of $A$. Typically, you show this by taking an arbitrary solution to $x$ and explicitly constructing a corresponding solution to $f(x)$.
• $(\Leftarrow)$ If $f(x)$ is a yes-instance of $A$, then $x$ is a yes-instance of $X$. You show this by taking a solution to $f(x)$ and explicitly constructing a corresponding solution to $x$. This is often the harder direction, since you need to consider all possible solutions to $f(x)$ (not just the ones you had in mind while making the reduction construction).

On the Direction of the Reduction

The most common way to lose points on an NP-completeness proof is to reduce the wrong way. If the reduction direction is flipped, then the entire content of the argument will be incorrect.

Recall what NP-hardness of $A$ requires: a reduction $X \le_P A$ from a known NP-hard problem $X$ into your target $A$. The operational meaning is that a fast algorithm for $A$ would yield a fast algorithm for $X$ (compute reduction $f(x)$, then call a solver for $A$). Since $X$ is already known to be hard, this transfers that hardness onto $A$.

Reducing the other way, $A \le_P X$, proves the opposite kind of statement. It says a fast algorithm for $X$ would solve $A$; that is, $A$ is no harder than $X$. This is an upper bound on $A$'s difficulty, not a lower bound. It places no floor on how hard $A$ is, so it establishes nothing about NP-hardness.

Example Problem: Independent Set

Independent Set: Given an undirected graph $G = (V, E)$ and integer $k$, we say that a set of nodes $S \subseteq V$ is independent if no two nodes in $S$ are joined by an edge. Does there exist an independent set of size at least $k$?

Show that Independent Set is NP-Complete.

We first show that Independent Set is in NP. Given a graph instance $G = (V, E)$ and certificate (proposed solution) $S$, we check that the following conditions are true. If any of them do not hold, then we output "no". Otherwise, we output "yes".

• Check that $S$ is at least size $k$ (verify $|S| \ge k$).
• For each pair of nodes $u, v \in S$ with $u \ne v$, ensure $(u, v) \notin E$. In other words, no node pair in $S$ should form an edge in $G$.

We observe that this verifier runs in polynomial time. Since $S \subseteq V$, checking the first condition takes $O(|V|)$ time. For the second condition, we consider all pairs of nodes in $S$ and check membership in $E$; there can be at most $O(|V|^2)$ pairs and a naive membership check in $E$ takes $O(|E|)$ time. Thus, our verifier runs in $O(|V|^2 \cdot |E|)$ time, which is indeed polynomial.

We show that Independent Set is NP-Hard by showing a reduction from 3SAT.

Recall that 3SAT gives a 3CNF (AND of ORs) of clauses with exactly three variables, where the 3CNF is satisfiable if there exists a boolean assignment of variables that satisfy all clauses. For example, the following 3CNF is satisfiable by setting $x_1$ and $x_3$ to be true and $x_{2}$ to be false (there are other satisfying sets of variable assignments).

$$\begin{align*} (x_1 \lor \lnot x_3 \lor x_2) \land (\lnot x_1 \lor \lnot x_3 \lor \lnot x_2) \land (\lnot x_1 \lor x_3 \lor x_2) \end{align*}$$

Given a 3CNF $\phi$ of $m$ clauses and $n$ variables, we create a graph $G$ that we can run an algorithm for Independent Set on. For clause $i$, we create 3 nodes $x_{ij_1}$, $x_{i j_2}$, and $x_{i j_3}$, representing the three literals in clause $i$. We connect these three nodes with edges forming a triangle. Additionally, for every pair of nodes representing a variable and its negation (i.e. $x_{ij}$ and $\lnot x_{ij}$) across all clauses, we add an edge between them. We set $k = m$.

We argue that this reduction takes polynomial time. For each of the $m$ clauses, we create 3 nodes and 3 edges (to connect them all together) in our graph. In addition, we connect all pair of nodes representing variables and their negation. There are at most $(3m)^2 = O(m^2)$ pairs possible, so we can reduce our 3SAT instance to an Independent Set instance in $O(m^2 + m) = O(m^2)$ time, which is polynomial.

The intuition is that each clause is represented by a gadget of "nodes" in our graph $G$. Since $k = m$ in our Independent Set instance, we must pick exactly one node from each clause gadget to be in the independent set $S$ (the triangle edges prevent picking two nodes from the same gadget). Picking a node $x_{ij}$ corresponds to setting that literal to true. The consistency edges between contradictory literal pairs ensure we never pick both a variable and its negation (which would violate the independent set property), so the assignment is well-defined and satisfies every clause.

The visualization below walks through this construction on a small 3CNF. Step through it to see the clause gadgets, triangle edges, and consistency edges appear.

3SAT → Independent Set

One gadget per clause

Each clause becomes a gadget of three nodes, one per literal. We have three clauses, so nine nodes in total. Nothing is connected yet.

Target size k3

(x₁ ∨ x₂ ∨ x₃) ∧ (¬x₁ ∨ x₄ ∨ x₅) ∧ (x₂ ∨ ¬x₄ ∨ x₆)

triangle edge consistency edge

$(\Rightarrow)$ Suppose the 3CNF $\phi$ is satisfiable. We show that a satisfying assignment of variables to a 3SAT instance implies an independent set solution to our constructed graph. Fix a satisfying assignment. For each clause $i$, at least one of its three literals is true under this assignment; pick one such true literal and include its corresponding node $x_{ij}$ in $S$. This gives $|S| = m \ge k$.

We check that $S$ is independent. No two nodes lie in the same clause gadget, since we picked exactly one per gadget (no triangle edges are present within $S$). Also, no two chosen nodes correspond to a variable and its negation: since both nodes would have to present true literals under the same assignment, a variable and its negation cannot both be true. Hence, no consistency edge connects two nodes of $S$. So $S$ is an independent set of size $m = k$.

$(\Leftarrow)$ Suppose $G$ has an independent set $S$ with $|S| = k = m$ (we know it cannot go any higher because exactly one node can be picked per clause gadget, and there are $m$ of them).

Define a variable assignment by setting each literal corresponding to a node in $S$ to true (if a variable has neither literal represented in $S$, then assign it arbitrarily). This assignment is well defined; if both $x_{ij}$ and $\lnot x_{i'j}$ were in $S$, it would not be an independent set because they are connected by an edge. So no variable is assigned conflicting values. Since $S$ contains one node per clause gadget, every cluase has at least one literal set to true, so every clause is satisfied. Hence $\phi$ is satisfiable.

Therefore, our 3CNF $\phi$ is satisfiable if and only if $G$ has an independent set of size $k = m$, completing the reduction. Combined with the polynomial-time verifier shown earlier, Independent Set is NP-complete.

Known NP-Complete Problems

The known NP-complete problems fall into several natural categories. On assignments or exams, you may freely cite NP-complete problems that have appeared in class, previous assignments, or in the textbook.

Packing Problems

If your problem has a parameter $k$ for which as $k$ gets larger the problem gets harder, try reducing from:

• Independent Set: Given an undirected graph $G = (V, E)$ and integer $k$, we say that a set of nodes $S \subseteq V$ is independent if no two nodes in $S$ are joined by an edge. Does there exist an independent set of size at least $k$?
• Set Packing: Given a universe $U$, subsets $S_1, \dots, S_m \subseteq U$, and an integer $k$, does there exists a subcollection of $\{S_1, \dots, S_m\}$ of at least $k$ pairwise-disjoint subsets?

Covering Problems

If your problem has a parameter $k$ for which as $k$ gets larger the problem gets easier, try reducing from:

• Vertex Cover: Given an undirected graph $G = (V, E)$ and an integer $k$, we say that a set of nodes $S \subseteq E$ if every edge $e \in E$ has at least one endpoint in $S$. Does there exist a vertex cover of size at most $k$?
• Set Cover: Given a universe $U$, subsets $S_1, \dots, S_m \subseteq U$, and an integer $k$, does there exist a subcollection of $\{S_1, \dots, S_m\}$ of at most $k$ sets whose union is all of $U$?

Partitioning Problems

If your problem involves dividing elements into disjoint groups, try reducing from:

• 3D Matching: Given disjoint sets $X, Y, Z$ each of size $n$, a set of triples $T \subseteq X \times Y \times Z$, does there exist a set of $n$ triples in $T$ such that every element of $X \cup Y \cup Z$ is contained in exactly one of these triples?
• 3-Coloring: Given an undirected graph $G = (V, E)$, does $G$ have a 3-coloring?

Sequencing Problems

If your problem involves giving an ordering over $n$ items, try reducing from:

• Hamiltonian Cycle: Given a graph $G$ (either directed or undirected), is there a Hamiltonian cycle (a path starts and ends with the same node and visits every other node exactly once)?
• Hamiltonian Path: Given a graph $G$ (either directed or undirected), start node $s$ and end node $t$, is there a Hamiltonian path starting at $s$ and ending at $t$?

Other

If your problem involves summing over numeral values to reach a target, try reducing from:

• Subset Sum: Given nonnegative integers $w_1, \dots, w_n$ and a target integer $W$, does there exist $I \subseteq \{1, \dots, n\}$ such that $\sum_{i \in I} w_i = W$?

If all else fails, try 3-SAT!

• 3SAT: Given a CNF with clauses of 3 literals each, does there exist a satisfying assignment?

Practice

Problem 1. [Graph Selection] Suppose we have a graph $G = (V, E)$. You are given two disjoint sets $E_{good}$ and $E_{bad}$, and a vertex set $C \subseteq V$. The Graph-Selection problem is to determine whether there exists a vertex set $P$ such that:

• $C \subseteq P$
• For all $v \in P$, there is a $u \in P$ such that $(u, v) \in E_{good}$
• For all $(u, v) \in E_{bad}$, either $u \notin P$ or $v \notin P$

Prove that Graph-Selection is NP-Complete. (Source: CS 4820 FA25 Prelim 2 Review)

Hint 1

Could we try a reduction from 3-SAT?

Hint 2

With our reduction from 3-SAT, create two nodes for setting a variable $x_i$ either true or false.

Hint 3

With the previous setup, what should our bad edge set $E_{bad}$ be?

Solution

We first show that Graph Selection is in NP. Given a Graph Selection instance consisting of graph $G = (V, E)$, edge sets $E_{good}$ and $E_{bad}$, and set $C \subseteq V$, we take in a certificate set $P$ and check the following conditions. If any of them are false, we reject $P$ (outputting "no"). Otherwise, if all conditions hold, output "yes".

• $C \in P$. This takes $O(|V|)$ time.
• For all $v \in P$, there is a $u \in P$ such that $(u, v) \in P_{good}$. We can check this by fixing each $v \in P$ and checking through all $u \in P$ with $u \ne v$ to see if $(u, v) \in E_{good}$; if no $u \in P$ satisfies this, then we can reject $P$. We enumerate of all possible pairs in $P \subseteq V$, so we take $O(|V|^2)$ time for this check.
• For all $(u, v) \in E_{bad}$, either $u \notin P$ or $v \notin P$. We check over all edges $(u, v) \in E_{bad}$. If there exists $e = (u', v')$ such that $u' \in P$ and $v' \in P$, then we reject $P$. Since $E_{bad} \subseteq E$, this step takes $O(|E|)$ time.

Our verifier has an overall runtime of $O(|V|^2 + |E|)$, which is indeed polynomial.

We show that Graph Selection is NP-Hard by showing a reduction from 3SAT.

Given a 3CNF $\phi$ of $m$ clauses and $n$ variables, we create a graph $G$ that we can run an algorithm for Graph Selection on. We create the following nodes

• For each variable $x_i$, we create two nodes $t_i$ and $f_i$.
• For each clause $C_j$, create a clause node $c_j$.
• Let $C = \{c_j : 1 \le j \le m \}$.

Next, we create the following edges.

• For every variable $x_i$, create an edge $(t_i, f_i)$. Let $E_{bad}$ be the set of all these edges.
• For every clause $C_j$ with corresponding node $v_j$, we create three edges and place them all in $E_{good}$. Let $x_a, x_b, x_c$ be the 3 variables in the clause. For each of the three variables: if some literal $x_i$ is in the clause, we put in edge $(c_j, t_i)$; otherwise, if some literal $\lnot x_i$ is in the clause, we put in edge $(c_j, f_i)$.

We run Graph-Selection on this input and output whatever it outputs. This reduction runs in polynomial time. We create $2n + m$ nodes and $n + 3m$ edges, which is polynomial in the size of the input 3CNF.

We now show that the original 3SAT instance $\phi$ has a solution iff this instance of Graph-Selection has a solution.

$(\Rightarrow)$ Satisfiable $\phi$ gives a valid $P$

Fix a satisfying assignment and let

$$P_0 \;=\; C \;\cup\; \{\, t_i : x_i \text{ TRUE} \,\} \;\cup\; \{\, f_i : x_i \text{ FALSE} \,\}.$$

Condition 1. $C \subseteq P_0$ by construction.

Condition 2. Let $v \in P_0$.

• If $v = c_j$: the assignment satisfies $C_j$, so some literal $\ell$ of $C_j$ is true. Let $w$ be its node ($t_i$ if $\ell = x_i$, else $f_i$). Then $(c_j, w) \in E_{good}$ by construction, and $w \in P_0$ since $\ell$ is true.
• If $v$ is a literal node: after preprocessing its literal occurs in some clause $C_j$, so $(c_j, v) \in E_{good}$ and $c_j \in C \subseteq P_0$.

Condition 3. $E_{bad} = \{(t_i,f_i)\}_{i=1}^{n}$, and the assignment gives each $x_i$ exactly one value, so at most one of $t_i, f_i$ lies in $P_0$. No bad edge has both endpoints in $P_0$.

Hence $P_0$ is a valid selection.

$(\Leftarrow)$ A valid $P$ gives a satisfying assignment

Given a valid $P$, define

$$x_i = \text{TRUE} \iff t_i \in P.$$

This is well defined, and it assigns every variable. Observe that $f_i \in P$ forces $t_i \notin P$, since $(t_i, f_i) \in E_{bad}$ and $P$ satisfies condition 3. So

$$f_i \in P \;\Longrightarrow\; x_i = \text{FALSE} \;\Longrightarrow\; \lnot x_i \text{ is true.}$$

Fix a clause $C_j$. Since $c_j \in C \subseteq P$, condition 2 gives some $u \in P$ with $(u, c_j) \in E_{good}$. Every good edge at $c_j$ leads to a node of one of $C_j$'s three literals, so $u$ is such a node.

• $u = t_i$: then $x_i = \text{TRUE}$, and the edge exists only because the literal $x_i$ occurs in $C_j$. Clause satisfied.
• $u = f_i$: then $x_i = \text{FALSE}$ by the observation, and $\lnot x_i$ occurs in $C_j$. Clause satisfied.

Every clause is satisfied, so $\phi$ is satisfiable.

Problem 2. [Monotone SAT] Consider the following variant of SAT. We say that a boolean formula is monotone if no variable appears negated; i.e. every literal is a positive occurence of some variable $x_i$. For example, the following SAT formula is monotone:

$$\begin{align*} (x_1 \lor x_2 \lor x_4) \land (x_2 \lor x_{23}) \land (x_7 \lor x_{10} \lor x_{100}) \end{align*}$$

We take as input a montone CNF formula $\phi = C_1 \land C_2 \land \dots \land C_n$ over variables $x_1, \dots, x_n$, where each $C_i$ consists of ORs of non-negated literals. We also take an input number $k$. The Monotone SAT decision problem asks whether $\phi$ is satisfiable by setting at most $k$ variables equal to true.

Prove that Monotone SAT is NP-Complete.

Hint

Use a reduction from Vertex Cover.

Solution

We first show that Monotone SAT is in NP. Given a Monotone SAT instance with boolean formula $\phi$ (made up of clauses of only positive literals) and a parameter $k$, we take a variable assignment as our certificate. We check the following conditions: the amount of variables set to true in the assignment is less than or equal to $k$, and every clause $C_i$ is satisfied. If any of these conditions are false, we reject the certificate. Otherwise, we accept.

We claim that this verifier runs in polynomial time. To check the first condition, we can perform a linear scan through all the variable assignments and count how many variables are assigned to true. For the second condition, checking each clause requires scanning its literals. For a formula with $n$ variables and $m$ clauses, this runs in $O(mn)$ time, which is polynomial. Thus, Monotone SAT is in NP.

Next, we show that Monotone SAT is NP-Hard by showing a reduction from Vertex Cover.

Recall the Vertex Cover problem: given a graph $G = (V, E)$ and an integer $k$, decide whether there is a set $S \subseteq V$ with $|S| \le k$ such that every edge has at least one endpoint in $S$.

For our reduction, consider an instance of Vertex Cover with graph $G = (V, E)$ and parameter $k$ with $V = (v_1, \dots, v_n)$. We create a variable $x_i$ for each vertex $v_i$. For each edge $e = (v_i, v_j) \in E$, create the clause $(x_i \lor x_j)$. Then, let

$$\begin{align*} \phi = \bigwedge_{(v_i, v_j) \in E} (x_i \lor x_j) \end{align*}$$

and keep $k$ the same. Every literal is a positive occurence of a variable, so $\phi$ is monotone. The construction produces one variable per vertex and one clause per edge, so it runs in polynomial time.

For correctness, we show that $(G, k)$ is a yes-instance of Vertex Cover iff $(\phi, k)$ is a yes-instance of Monotone SAT.

$(\Rightarrow)$ Suppose $S$ is a vertex cover with $|S| \le k$. Set $x_i =$ true exactly when $v_i \in S$. This sets at most $k$ variables true. For any clause $(x_i \lor x_j)$ corresponding to edge $(v_i, v_j)$, since $S$ covers this edge, at least one of $v_i, v_j \in S$, so at least one of $x_i, x_j$ is true and the clause is satisfied. Thus, $\phi$ is satisfied with at most $k$ true variables.

$(\Leftarrow)$ Suppose $\phi$ is satisfied by an assignment with at most $k$ true variables. Let $S = \{v_i: x_i = \text{true}\}. so$|S| \le k$. For any edge$(v_i, v_j)$, the clause$(x_i \lor x_j)$is satisfied, so at least one of$x_i, x_j$is true, meaning at least one of$v_i, v_j \in S$. Hence,$S$covers every edge is a vertex cover of size at most$k$.

Since the reduction runs in polynomial time and is correct, Vertex Cover $\le_P$ Monotone SAT, so Monotone SAT is NP-Hard.

Monotone SAT is in NP and is NP-Hard, so it is NP-Complete.

Problem 3. [3-Coloring] Given a graph $G = (V, E)$, the 3-Coloring problem asks if there is an assignment of colors to the nodes of the graph such that no two adjacent vertices have the same color, and at most 3 colors are used.

Prove that 3-Coloring is NP-Complete.

Solution

We first show that 3-Coloring is in NP. Given a 3-Coloring instance of a graph $G = (V, E)$, we take as input to our verifier a coloring assignment $c: V \rightarrow \{1, 2, 3\}$. The verifier iterates over every edge $(u, v) \in E$ and checks that $c(u) \ne c(v)$. If every edge has properly colored endpoints, accept; otherwise, reject. This runs in $O(|E|)$ time, so our verifier is indeed polynomial.

We now show that 3-Coloring is NP-Hard by providing a reduction from 3SAT. Let $\phi$ be a 3CNF formula.

In progress!

Problem 4. [Partition] The input to the Partition problem is a set of $n$ large integers $w_1, \dots, w_n$. The problem is to decide if there is a subset $I \subset \{1, \dots, n\}$ such that $\sum_{i \in I} w_i = \sum_{i \notin I} w_i$.

Show that Partition is NP-Complete.

Hint

Reduce from Subset Sum.

Solution

We first show that Partition is in NP. Given a Partition instance of $n$ large numbers $w_1, \dots, w_n$, our certificate is a set $I$. We can simply check if $\sum_{i \in I} w_i = \sum_{i \notin I} w_i$ holds (if yes, then accept; otherwise, reject this certificate). If we use $w = \max_i w_i$, then doing $O(n)$ addition operations and checking if the sums are equivalent takes $O(n \log w)$ time. This is polynomial in the input size.

We show that Partition is NP-Hard by showing a reduction from Subset Sum.

Let numbers $a_1, \dots, a_n$ with target sum $A$ be a Subset Sum instance. First, we add up all numbers and let $\overline{A} = \sum_{i = 1}^n a_i - A$. We assume without loss of generality that $A \ge \overline{A}$. We create an input to Partition that uses $n + 1$ numbers: $a_1, \dots, a_n$ from Subset Sum and one additional number $a_{n + 1} = A - \overline{A}$.

Letting $a = \max_i a_i$, this reduction takes $O(n \log a)$, as we need to do $O(n)$ addition/subtraction operations to create our new element $a_{n + 1}$ (since these are large numbers, we take $O(\log a)$ time for each addition operation). Therefore, our reduction runs in polynomial time.

The intuition for this reduction is as follows: if there exists such a subset $I$ such that $\sum_{i \in I} a_i = A$, then the remaining elements sum to $\overline{A} = \sum_{i = 1}^n a_i - A$. So a yes-instance of Subset Sum splits the numbers into two groups with sums $A$ and $\overline{A}$. This is almost a partition; both sides aren't always balanced, they differ by $A - \overline{A}$. Adding in an extra number $a_{n + 1} = A - \overline{A}$ closes this gap on the $\overline{A}$ side and makes the two sums equal to $A$. In other words, $a_{n + 1} = A - \overline A$ is a "balancing weight" that turns an uneven Subset Sum split into an even partitioning.

$(\Rightarrow)$ Suppose there is a subset $I$ of the subset sum problem with total sum $A$. Then this subset satisfies the parition rule for the input we created. Since we have $\sum_{i = 1}^{n + 1} a_i = 2A$, the remaining items not selected in $I$ will sum to $A$. Thus, we have a solution to Partition.

$(\Leftarrow)$ Suppose our constructed Partition instance has a partition of the $n + 1$ numbers with equal sums. Note that $\sum_{i = 1}^{n + 1}a_i = 2A$ implies that both sides sum to $A$. We simply chose subset $I$ to be the side of the partition not containing the newly created item $a_{n + 1}$, so $I$ is a solution to the Subset Sum problem.

Since we have shown Partition to be in NP and NP-Hard, this problem is NP-Complete as required. $\square$