[proofplan] We use the total polynomial-time many-one reduction from $A$ to $B$ as a preprocessing step. Given an input word over the alphabet of $A$, compute its reduction output over the alphabet of $B$ and then run a polynomial-time decider for $B$ on that output. Correctness follows directly from the defining membership equivalence supplied by the reduction, and the running time remains polynomial because the reduction output has length bounded by the time required to compute it. [/proofplan] [step:Choose a polynomial-time reduction and a polynomial-time decider for $B$] Let $\Sigma_A$ and $\Sigma_B$ denote the finite alphabets over which the languages $A \subseteq \Sigma_A^*$ and $B \subseteq \Sigma_B^*$ are defined. The notation $A \le_m^p B$ means that $A$ is polynomial-time many-one reducible to $B$: there is a total polynomial-time computable map from words over $\Sigma_A$ to words over $\Sigma_B$ that preserves membership in the target language. Thus, by the definition of polynomial-time many-one reduction, since $A \le_m^p B$, there exists a total function \begin{align*} f: \Sigma_A^* \to \Sigma_B^* \end{align*} computed by a deterministic Turing machine $M_f$ in polynomial time such that, for every $x \in \Sigma_A^*$, \begin{align*} x \in A \iff f(x) \in B. \end{align*} Since $B \in \mathrm P$, by the definition of the class $\mathrm P$, there exists a deterministic Turing machine $M_B$ deciding $B$ in polynomial time. Thus there is a polynomial $q: \mathbb N \to \mathbb N$ such that, for every $y \in \Sigma_B^*$, the machine $M_B$ halts on input $y$ within $q(|y|)$ steps and accepts exactly when $y \in B$. [guided] Let $\Sigma_A$ and $\Sigma_B$ denote the finite alphabets over which the languages $A \subseteq \Sigma_A^*$ and $B \subseteq \Sigma_B^*$ are defined. The notation $A \le_m^p B$ means that $A$ is polynomial-time many-one reducible to $B$. The definition of polynomial-time many-one reduction says that this hypothesis supplies exactly two pieces of data. First, it supplies a total computable map \begin{align*} f: \Sigma_A^* \to \Sigma_B^* \end{align*} whose values are computable in polynomial time by some deterministic Turing machine $M_f$. Second, it supplies the membership-preserving equivalence \begin{align*} x \in A \iff f(x) \in B \end{align*} for every word $x \in \Sigma_A^*$. The definition of the class $\mathrm P$ says that the hypothesis $B \in \mathrm P$ supplies a deterministic polynomial-time decider for $B$. Concretely, there is a deterministic Turing machine $M_B$ and a polynomial $q: \mathbb N \to \mathbb N$ such that $M_B$ halts on every input $y \in \Sigma_B^*$ within $q(|y|)$ steps. Its decision rule is exact: $M_B$ accepts $y$ if and only if $y \in B$. These are the only ingredients needed. The reduction converts the question “is $x$ in $A$?” into the equivalent question “is $f(x)$ in $B$?”, and the decider $M_B$ answers the latter question in polynomial time. [/guided] [/step] [step:Construct a decider for $A$ by composing the reduction with the decider for $B$] Define a deterministic Turing machine $M_A$ as follows. On input $x \in \Sigma_A^*$, the machine $M_A$ first runs $M_f$ on $x$ and writes the resulting word $f(x) \in \Sigma_B^*$ on its work tape. It then runs $M_B$ on input $f(x)$. The machine $M_A$ accepts $x$ if and only if $M_B$ accepts $f(x)$, and rejects otherwise. This machine halts on every input because $M_f$ halts on every input and $M_B$ halts on every input. [/step] [step:Verify that the constructed machine decides $A$] Let $x \in \Sigma_A^*$ be arbitrary. By construction, $M_A$ accepts $x$ if and only if $M_B$ accepts $f(x)$. Since $f(x) \in \Sigma_B^*$ and $M_B$ decides $B \subseteq \Sigma_B^*$, this is equivalent to $f(x) \in B$. By the defining property of the many-one reduction $f$, this is equivalent to $x \in A$. Hence $M_A$ accepts exactly the words in $A$, so $M_A$ decides $A$. [/step] [step:Bound the running time by a polynomial in the input length] Because $M_f$ runs in polynomial time, there is a polynomial $p: \mathbb N \to \mathbb N$ such that, for every $x \in \Sigma_A^*$, the computation of $M_f$ on $x$ halts within $p(|x|)$ steps. Since a Turing machine can output at most one tape symbol per step, the output length satisfies \begin{align*} |f(x)| \le p(|x|). \end{align*} The second stage runs $M_B$ on $f(x)$, so its running time is at most \begin{align*} q(|f(x)|). \end{align*} Using $|f(x)| \le p(|x|)$, and replacing $q$ by a nondecreasing polynomial upper bound if necessary, this is at most \begin{align*} q(p(|x|)). \end{align*} Therefore the total running time of $M_A$ on input $x$ is at most \begin{align*} p(|x|) + q(p(|x|)). \end{align*} The function $r: \mathbb N \to \mathbb N$ defined by \begin{align*} r(n) = p(n) + q(p(n)) \end{align*} is a polynomial. Thus $M_A$ runs in polynomial time. [/step] [step:Conclude that $A$ belongs to $\mathrm P$] We have constructed a deterministic Turing machine $M_A$ that halts on every input, decides $A$, and runs in time bounded by the polynomial $r$. Therefore $A \in \mathrm P$. [/step]