[proofplan]
We first prove that $\mathrm{PARTITION}$ lies in $\mathrm{NP}$ by using one side of a proposed partition as a certificate and checking equality of the two sums in polynomial time. For NP-hardness, we give a polynomial-time many-one reduction from the subset-sum problem, after separately handling targets larger than the total available sum. The reduction appends two carefully chosen positive integers to the original list so that any equal partition must place exactly one appended integer on each side. Reading off the original entries on the side containing the larger appended term recovers precisely a subset-sum solution.
[/proofplan]
[step:Verify membership in NP using one side of the partition]
Let $b_1,\dots,b_m$ be an input list of positive integers, and let $B$ denote its total sum:
\begin{align*}
B := \sum_{j=1}^{m} b_j.
\end{align*}
A certificate is a subset $J \subset \{1,\dots,m\}$, encoded for instance by its characteristic bit string of length $m$. Given $J$, the verifier computes
\begin{align*}
S_J := \sum_{j \in J} b_j
\end{align*}
and accepts exactly when $2S_J = B$.
The sum $S_J$ and the total sum $B$ can be computed by binary integer addition in time polynomial in the bit length of the input. Hence a yes-instance has a polynomial-size certificate verifiable in polynomial time, so $\mathrm{PARTITION} \in \mathrm{NP}$.
[guided]
We need to show that a proposed solution to a $\mathrm{PARTITION}$ instance can be checked efficiently. The input is a finite list of positive integers $b_1,\dots,b_m$, and the question is whether some subset of the indices gives one side of an equal partition. Define the total sum
\begin{align*}
B := \sum_{j=1}^{m} b_j.
\end{align*}
A natural certificate is the set of indices $J \subset \{1,\dots,m\}$ claimed to lie on one side of the partition. We encode $J$ as a bit string of length $m$, where the $j$th bit records whether $j \in J$.
The verifier computes the proposed side sum
\begin{align*}
S_J := \sum_{j \in J} b_j.
\end{align*}
The complementary side has sum $B - S_J$, so the two sides are equal exactly when $S_J = B - S_J$, equivalently when $2S_J = B$. Binary addition and comparison of integers whose bit lengths are bounded by the input length take polynomial time. Therefore the certificate has polynomial length and can be verified in polynomial time. This proves $\mathrm{PARTITION} \in \mathrm{NP}$.
[/guided]
[/step]
[step:Define the polynomial-time reduction from subset sum]
We reduce from $\mathrm{SUBSET}\text{-}\mathrm{SUM}$, whose input is a finite list of positive integers $a_1,\dots,a_n$ and a target integer $t \ge 0$, all encoded in binary. Let
\begin{align*}
A := \sum_{i=1}^{n} a_i.
\end{align*}
If $t>A$, then the subset-sum instance is a no-instance because every subset sum is at most $A$; in this case define the reduction to output the fixed no-instance $(1,2)$ of $\mathrm{PARTITION}$.
Assume now that $0 \le t \le A$. Define the output list
\begin{align*}
b_1,\dots,b_{n+2} := a_1,\dots,a_n,A+t,2A-t.
\end{align*}
The two appended integers are positive, since $A \ge 1$, $t \ge 0$, and $t \le A$. Their binary lengths are polynomially bounded by the binary lengths of $a_1,\dots,a_n,t$, because $A$ is computed by adding the input integers. Thus the map from $(a_1,\dots,a_n,t)$ to $(b_1,\dots,b_{n+2})$ is computable in polynomial time.
[/step]
[step:Convert a subset-sum solution into an equal partition]
Assume $0 \le t \le A$ and suppose there exists a subset $I \subset \{1,\dots,n\}$ such that
\begin{align*}
\sum_{i \in I} a_i = t.
\end{align*}
Let $J \subset \{1,\dots,n+2\}$ be the subset consisting of the index $n+2$, corresponding to the appended integer $2A-t$, together with the original indices in $I$:
\begin{align*}
J := I \cup \{n+2\}.
\end{align*}
Then the sum over $J$ is
\begin{align*}
\sum_{j \in J} b_j = \sum_{i \in I} a_i + (2A-t) = t + 2A - t = 2A.
\end{align*}
The total sum of the constructed partition instance is
\begin{align*}
\sum_{j=1}^{n+2} b_j = A + (A+t) + (2A-t) = 4A.
\end{align*}
Therefore the complement of $J$ also has sum $4A-2A=2A$, so the constructed instance is a yes-instance of $\mathrm{PARTITION}$.
[/step]
[step:Recover a subset-sum solution from any equal partition]
Assume $0 \le t \le A$ and suppose the constructed list $b_1,\dots,b_{n+2}$ has an equal partition. Thus there exists $J \subset \{1,\dots,n+2\}$ such that
\begin{align*}
\sum_{j \in J} b_j = 2A.
\end{align*}
The two appended indices $n+1$ and $n+2$ cannot both lie in $J$, because then
\begin{align*}
b_{n+1}+b_{n+2} = (A+t)+(2A-t)=3A>2A.
\end{align*}
They also cannot both lie outside $J$, because then both appended integers lie in the complement, whose sum is also $2A$, and the same inequality gives a contradiction. Hence exactly one of $n+1$ and $n+2$ lies in $J$.
If $n+1 \in J$ and $n+2 \notin J$, replace $J$ by its complement $J^c := \{1,\dots,n+2\}\setminus J$. This replacement preserves the property of being one side of an equal partition and makes $n+2 \in J^c$. Thus, without changing the partition, we may assume $n+2 \in J$ and $n+1 \notin J$.
Define
\begin{align*}
I := J \cap \{1,\dots,n\}.
\end{align*}
Since $J$ has sum $2A$ and contains $n+2$ but not $n+1$, we obtain
\begin{align*}
2A = \sum_{j \in J} b_j = \sum_{i \in I} a_i + (2A-t).
\end{align*}
Subtracting $2A-t$ from both sides gives
\begin{align*}
\sum_{i \in I} a_i = t.
\end{align*}
Thus the original subset-sum instance is a yes-instance.
[guided]
The purpose of the two added numbers is to force the partition to put one added number on each side. Let $J \subset \{1,\dots,n+2\}$ be one side of an equal partition, so its sum is $2A$ because the total constructed sum is $4A$.
First, the appended indices $n+1$ and $n+2$ cannot both lie in $J$. Indeed,
\begin{align*}
b_{n+1}+b_{n+2} = (A+t)+(2A-t)=3A.
\end{align*}
Since $A=\sum_{i=1}^{n}a_i$ is positive, $3A>2A$, so merely including both appended numbers would already exceed the required side sum $2A$. Therefore they cannot both lie in $J$.
They also cannot both lie outside $J$. If they were both outside $J$, then they would both lie in the complementary side. The complementary side also has sum $2A$, because $J$ is one side of an equal partition. But the same computation shows that the two appended numbers alone have sum $3A>2A$, again impossible. Hence exactly one of $n+1$ and $n+2$ appears on each side.
Now choose the side that contains the appended number $2A-t$. If $J$ already contains $n+2$, keep $J$. If instead $J$ contains $n+1$, replace $J$ by its complement
\begin{align*}
J^c := \{1,\dots,n+2\}\setminus J.
\end{align*}
The complement is also one side of the same equal partition, and it contains $n+2$. Thus we may work with a side, still denoted $J$, satisfying $n+2 \in J$ and $n+1 \notin J$.
The original indices lying on this side form the subset
\begin{align*}
I := J \cap \{1,\dots,n\}.
\end{align*}
Since the side $J$ has total sum $2A$, and since its only appended contribution is $b_{n+2}=2A-t$, we have
\begin{align*}
2A = \sum_{j \in J} b_j = \sum_{i \in I} a_i + (2A-t).
\end{align*}
Subtracting $2A-t$ gives
\begin{align*}
\sum_{i \in I} a_i = t.
\end{align*}
Therefore $I$ is a subset-sum solution for the original instance.
[/guided]
[/step]
[step:Conclude NP-hardness and NP-completeness]
For every subset-sum instance with $t>A$, the reduction outputs the fixed no-instance $(1,2)$ of $\mathrm{PARTITION}$, and the original instance is also a no-instance. For every instance with $0 \le t \le A$, the preceding two steps prove that
\begin{align*}
(a_1,\dots,a_n,t) \in \mathrm{SUBSET}\text{-}\mathrm{SUM} \iff (a_1,\dots,a_n,A+t,2A-t) \in \mathrm{PARTITION}.
\end{align*}
Hence $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ polynomial-time many-one reduces to $\mathrm{PARTITION}$. Since $\mathrm{SUBSET}\text{-}\mathrm{SUM}$ is NP-complete (citing a result not yet in the wiki: Subset Sum is NP-complete), $\mathrm{PARTITION}$ is NP-hard. Together with $\mathrm{PARTITION} \in \mathrm{NP}$, this proves that $\mathrm{PARTITION}$ is NP-complete.
[/step]
