[proofplan] We use the polynomial-time reduction as a preprocessing step. Given an input word $x$, compute the reduced instance $f(x)$ and then run a polynomial-time decider for $B$ on that instance. Correctness follows directly from the reduction equivalence, and the running time remains polynomial because the reduction produces its output in polynomial time, so the output length is polynomially bounded in the input length. [/proofplan] [step:Choose a polynomial-time reduction and a polynomial-time decider for $B$] Since $A \le_p B$, 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 A \iff f(x) \in B. \end{align*} Let $F$ be a deterministic algorithm computing $f$. Thus, on input $x \in \Sigma^*$, the algorithm $F$ halts with output $f(x)$ in time at most $p(|x|)$ for some polynomial \begin{align*} p: \mathbb{N} \to \mathbb{N}. \end{align*} Since $B \in P$, there exists a deterministic decider $M_B$ for $B$ and a polynomial \begin{align*} q: \mathbb{N} \to \mathbb{N} \end{align*} such that, for every $y \in \Sigma^*$, the machine $M_B$ halts on input $y$ in time at most $q(|y|)$ and accepts exactly when $y \in B$. [/step] [step:Construct the composed decider for $A$] Define a deterministic algorithm $M_A$ on input $x \in \Sigma^*$ as follows. First run $F$ on $x$ and denote its output by \begin{align*} y := f(x) \in \Sigma^*. \end{align*} Then run $M_B$ on input $y$. The algorithm $M_A$ accepts $x$ exactly when $M_B$ accepts $y$, and rejects $x$ exactly when $M_B$ rejects $y$. The algorithm $M_A$ halts on every input because $F$ halts on every input and $M_B$ halts on every input. [/step] [step:Verify that the composed decider recognizes exactly $A$] Let $x \in \Sigma^*$ be arbitrary, and let $y := f(x)$. By construction, $M_A$ accepts $x$ iff $M_B$ accepts $y$. Since $M_B$ decides $B$, this is equivalent to $y \in B$. Since $f$ is a polynomial-time many-one reduction from $A$ to $B$, this is equivalent to $x \in A$. Therefore, for every $x \in \Sigma^*$, \begin{align*} M_A \text{ accepts } x \iff x \in A. \end{align*} Thus $M_A$ decides $A$. [/step] [step:Bound the running time of the composed decider by a polynomial] Let $x \in \Sigma^*$ and set $n := |x|$. The first stage, computing $f(x)$, takes at most $p(n)$ steps. Since an algorithm cannot write more than one output symbol per step, the output word $y := f(x)$ satisfies \begin{align*} |y| \le p(n). \end{align*} The second stage, running $M_B$ on $y$, takes at most \begin{align*} q(|y|) \le q(p(n)) \end{align*} steps, after replacing $q$ by a nondecreasing polynomial upper bound if necessary. Hence the total running time of $M_A$ on inputs of length $n$ is at most \begin{align*} p(n) + q(p(n)). \end{align*} The map $n \mapsto p(n) + q(p(n))$ is a polynomial, so $M_A$ runs in polynomial time. [guided] Let $x \in \Sigma^*$ be an input word, and define its length by \begin{align*} n := |x|. \end{align*} The composed algorithm $M_A$ has two stages: it first computes $f(x)$ using $F$, and then it runs the decider $M_B$ on the resulting word. The first stage takes at most $p(n)$ steps by the polynomial-time computability of $f$. Now define \begin{align*} y := f(x) \in \Sigma^*. \end{align*} We need a bound on the time needed by $M_B$ on input $y$. The running time guarantee for $M_B$ is measured in terms of $|y|$, not in terms of $|x|$, so we must relate the length of the reduced instance to the length of the original instance. Since $F$ outputs $y$ within at most $p(n)$ steps, and a deterministic algorithm can write at most one output symbol in a single step, the number of symbols written is at most the number of steps taken. Therefore \begin{align*} |y| \le p(n). \end{align*} The machine $M_B$ runs on input $y$ in time at most $q(|y|)$. Replacing $q$ by a nondecreasing polynomial upper bound if necessary, the inequality $|y| \le p(n)$ gives \begin{align*} q(|y|) \le q(p(n)). \end{align*} Thus the total running time of $M_A$ is bounded by the time for the reduction plus the time for the decider for $B$: \begin{align*} p(n) + q(p(n)). \end{align*} Because the composition of polynomials is a polynomial and the sum of polynomials is a polynomial, the function $n \mapsto p(n) + q(p(n))$ is a polynomial. Hence $M_A$ runs in polynomial time. [/guided] [/step] [step:Conclude that $A$ lies in $P$] The algorithm $M_A$ is a deterministic decider for $A$, and its running time is bounded by a polynomial in the input length. Therefore $A \in P$. [/step]