[proofplan]
We prove equality of complexity classes by proving both inclusions. The inclusion $P \subseteq NP$ follows directly from the definitions, since a deterministic polynomial-time decision algorithm gives a polynomial-time verifier that ignores the certificate. For the reverse inclusion, take an arbitrary language $B \in NP$, reduce it to the $NP$-hard language $A$, and then decide $B$ by composing the polynomial-time reduction with a polynomial-time decision algorithm for $A$.
[/proofplan]
[step:Use deterministic algorithms as polynomial-time verifiers]
Let $B \subseteq \Sigma^*$ be a language with $B \in P$. By definition, there exist a deterministic Turing machine $M$ and a polynomial $p: \mathbb{N} \to \mathbb{N}$ such that, for every input word $x \in \Sigma^*$, the machine $M$ decides whether $x \in B$ in at most $p(|x|)$ steps.
Define a verifier machine $V$ as follows: on input pair $(x,c) \in \Sigma^* \times \Sigma^*$, where $c$ is a certificate word, the machine $V$ ignores $c$ and simulates $M$ on $x$. Then $V$ runs in time at most $p(|x|)$, hence in polynomial time in $|x| + |c|$, and satisfies
\begin{align*}
x \in B \iff \exists c \in \Sigma^* \text{ such that } V(x,c) \text{ accepts}.
\end{align*}
Indeed, if $x \in B$, then $M$ accepts $x$, so $V(x,c)$ accepts for every certificate $c$; if $x \notin B$, then $M$ rejects $x$, so $V(x,c)$ rejects for every certificate $c$. Thus $B \in NP$. Since $B \in P$ was arbitrary, $P \subseteq NP$.
[guided]
We first justify the easier inclusion $P \subseteq NP$ from the definitions. Let $B \subseteq \Sigma^*$ be any language in $P$. This means there is a deterministic Turing machine $M$ and a polynomial $p: \mathbb{N} \to \mathbb{N}$ such that $M$ decides membership in $B$ and halts on every input word $x \in \Sigma^*$ within $p(|x|)$ steps.
To show $B \in NP$, we need a polynomial-time verifier. Define
\begin{align*}
V: \Sigma^* \times \Sigma^* &\to \{\mathrm{accept}, \mathrm{reject}\}
\end{align*}
to be the verifier that takes an input word $x \in \Sigma^*$ and a certificate word $c \in \Sigma^*$, ignores $c$, and runs $M$ on $x$. The running time of $V$ is at most $p(|x|)$, which is also bounded by a polynomial in the total input length $|x| + |c|$.
Now check the verifier condition. If $x \in B$, then $M$ accepts $x$, so $V(x,c)$ accepts for any choice of certificate $c \in \Sigma^*$. If $x \notin B$, then $M$ rejects $x$, so no certificate can make $V(x,c)$ accept. Therefore
\begin{align*}
x \in B \iff \exists c \in \Sigma^* \text{ such that } V(x,c) \text{ accepts}.
\end{align*}
This proves $B \in NP$. Since the language $B \in P$ was arbitrary, we conclude $P \subseteq NP$.
[/guided]
[/step]
[step:Reduce an arbitrary $NP$ language to the polynomial-time language $A$]
Let $B \subseteq \Sigma^*$ be arbitrary with $B \in NP$. Since $A$ is $NP$-hard under polynomial-time many-one reductions, there exists a polynomial-time computable map
\begin{align*}
f: \Sigma^* &\to \Sigma^*
\end{align*}
such that, for every $x \in \Sigma^*$,
\begin{align*}
x \in B \iff f(x) \in A.
\end{align*}
Since $A \in P$, there exist a deterministic Turing machine $M_A$ and a polynomial $q: \mathbb{N} \to \mathbb{N}$ such that $M_A$ decides membership in $A$ in at most $q(|y|)$ steps on every input word $y \in \Sigma^*$.
Let $r: \mathbb{N} \to \mathbb{N}$ be a polynomial time bound for computing $f$. Because $f$ is computed in at most $r(|x|)$ steps, the output length satisfies $|f(x)| \le r(|x|)$ for every $x \in \Sigma^*$.
Define a deterministic decision machine $M_B$ for $B$ as follows: on input $x \in \Sigma^*$, compute $f(x)$, then run $M_A$ on $f(x)$, and accept exactly when $M_A$ accepts. The running time is at most
\begin{align*}
r(|x|) + q(|f(x)|) \le r(|x|) + q(r(|x|)).
\end{align*}
The function $n \mapsto r(n) + q(r(n))$ is a polynomial, so $M_B$ runs in polynomial time. The equivalence defining the reduction gives
\begin{align*}
M_B \text{ accepts } x \iff f(x) \in A \iff x \in B.
\end{align*}
Therefore $B \in P$.
[/step]
[step:Conclude equality of the two complexity classes]
The preceding step proves that every language $B \in NP$ belongs to $P$, so $NP \subseteq P$. The first step proved $P \subseteq NP$. Hence
\begin{align*}
P = NP.
\end{align*}
This proves the theorem.
[/step]
