To show that any problem $A$ is NP-Complete, we need to show four things:
(1) there is a non-deterministic polynomial-time algorithm that solves $A$, i.e., $A \in \mathrm{NP}$,
(2) any NP-Complete problem $B$ can be reduced to $A$,
(3) the reduction of $B$ to $A$ works in polynomial time,
(4) the original problem $A$ has a solution if and only if $B$ has a solution.
We now show that SET-PARTITION is NP-Complete.
(1) SET-PARTITION $\in \mathrm{NP}$ : Guess the two partitions and verify that the two have equal sums.
(2) Reduction of SUBSET-SUM to SET-PARTITION: Recall SUBSET-SUM is defined as follows: Given a set $X$ of integers and a target number $t$, find a subset $Y \subseteq X$ such that the members of $Y$ add up to exactly $t .$ Let $s$ be the sum of members of $X$. Feed $X^{\prime}=X \cup{s-2 t}$ into SET-PARTITION. Accept if and only if SET-PARTITION accepts.
(3) This reduction clearly works in polynomial time.
(4) We will prove that $\langle X, t\rangle \in$ SUBSET-SUM iff $\left\langle X^{\prime}\right\rangle \in$ SET-PARTITION. Note that the sum of members of $X^{\prime}$ is $2 s-2 t$.
$\Rightarrow:$ If there exists a set of numbers in $X$ that sum to $t$, then the remaining numbers in $X$ sum to $s-t$. Therefore, there exists a partition of $X^{\prime}$ into two such that each partition sums to $s-t$.
$\Leftarrow$ : Let’s say that there exists a partition of $X^{\prime}$ into two sets such that the sum over each set is $s-t$. One of these sets contains the number $s-2 t$. Removing this number, we get a set of numbers whose sum is $t$, and all of these numbers are in $X$.

(1) DOUBLE-SAT $\in \mathrm{NP}$ : Simply guess two different assignments to all variables and verify that each clause is satisfied in both cases.
(2) Reduction of $3 S A T$ to DOUBLE-SAT: Given a 3 cnf-function $\psi$, create a new Boolean function $\psi^{\prime}$ by adding a new clause $(x \cup \bar{x})$ to $\psi$, where $x$ is a new variable not in $\psi$. Then check if $\left\langle\psi^{\prime}\right\rangle \in D O U B L E-S A T$.
(3) This reduction clearly works in polynomial time.
(4) We now prove that the original 3 cnf-function $\langle\psi\rangle \in 3 S A T$ iff the new Boolean function $\left\langle\psi^{\prime}\right\rangle \in D O U B L E-S A T .$ If the original 3 cnf-function $\psi$ is unsatisfiable, then the new function $\psi^{\prime}$ is also unsatisfiable; i.e., $\langle\psi\rangle \notin 3 S A T$ implies $\left\langle\psi^{\prime}\right\rangle \notin$ DOUBLE-SAT. If $\langle\psi\rangle \in 3 S A T$, then use the same assignment of variables that are in $\psi$, and we also have both $x=0$ and $x=1$ are valid assignments. Thus, there are at least two satisfying assignments of the augmented 3 cnf-formula $\psi^{\prime}$, so $\left\langle\psi^{\prime}\right\rangle \in D O U B L E-S A T$.

First, $L P A T H \in \mathrm{NP}$ because we can guess a simple path of length at least $k$

from $a$ to $b$ and verify it in polynomial time. Next $U H A M P A T H \leq_{\mathrm{P}} L P A T H$, because the following TM $F$ computes the reduction $f$.
$F=$ “On input $\langle G, a, b\rangle$ where graph $G$ has nodes $a$ and $b:$

1. Let $k$ be the number of nodes of $G$.
2. Output $\langle G, a, b, k\rangle$.
   If $\langle G, a, b\rangle \in U H A M P A T H$, then $G$ contains a Hamiltonian path of length $k$ from $a$ to $b$, so $\langle G, a, b, k\rangle \in L P A T H .$ If $\langle G, a, b, k\rangle \in L P A T H$, then $G$ contains a simple path of length $k$ from $a$ to $b .$ But $G$ has only $k$ nodes, so the path is Hamiltonian. Thus, $\langle G, a, b\rangle \in U H A M P A T H$.