[proofplan] Choose deterministic polynomial-time deciders for $L_1$ and $L_2$. To decide the union and intersection, run both machines on the same input and combine their two Boolean answers by the corresponding Boolean operation. To decide the complement of $L_1$, run the decider for $L_1$ and reverse its accepting and rejecting outcomes. In each case, halting is inherited from the original deciders, and the running time is bounded by a polynomial obtained from the original polynomial bounds. [/proofplan] [step:Choose polynomial-time deciders for the two languages] By the definition of the class $\mathrm{P}$, since $L_1 \in \mathrm{P}$, there exist a deterministic polynomial-time decider $M_1$ and a polynomial function $p_1: \mathbb{N} \to \mathbb{N}$ such that, for every word $w \in \Sigma^*$, the machine $M_1$ halts on input $w$ within $p_1(|w|)$ steps and accepts $w$ if and only if $w \in L_1$. Again by the definition of the class $\mathrm{P}$, since $L_2 \in \mathrm{P}$, there exist a deterministic polynomial-time decider $M_2$ and a polynomial function $p_2: \mathbb{N} \to \mathbb{N}$ such that, for every word $w \in \Sigma^*$, the machine $M_2$ halts on input $w$ within $p_2(|w|)$ steps and accepts $w$ if and only if $w \in L_2$. Choose a constant $c_0 \in \mathbb{N}$ that bounds the fixed number of transition steps needed, after the two simulations have halted, to combine their accept/reject answers for either Boolean operation. Define $q: \mathbb{N} \to \mathbb{N}$ by \begin{align*} q(n) = p_1(n) + p_2(n) + c_0. \end{align*} Choose a constant $c_1 \in \mathbb{N}$ that bounds the fixed number of transition steps needed, after the simulation of $M_1$ has halted, to reverse its accept/reject answer. Define $r: \mathbb{N} \to \mathbb{N}$ by \begin{align*} r(n) = p_1(n) + c_1. \end{align*} Because sums of polynomial functions and constant functions are polynomial functions, both $q$ and $r$ are polynomial functions. [/step] [step:Decide the union by accepting when either decider accepts] Define a deterministic Turing machine $M_{\cup}$ as follows. On input $w \in \Sigma^*$, first run $M_1$ on $w$, then run $M_2$ on $w$. Accept if at least one of these two computations accepts, and reject otherwise. For every $w \in \Sigma^*$, both simulations halt, so $M_{\cup}$ halts. Its running time is at most \begin{align*} p_1(|w|) + p_2(|w|) + c_0 = q(|w|) \end{align*} steps, since the final Boolean check is included in the definition of $c_0$. Moreover, \begin{align*} M_{\cup} \text{ accepts } w \iff M_1 \text{ accepts } w \text{ or } M_2 \text{ accepts } w. \end{align*} By the choice of $M_1$ and $M_2$, this is equivalent to \begin{align*} w \in L_1 \text{ or } w \in L_2, \end{align*} which is equivalent to $w \in L_1 \cup L_2$. Therefore $M_{\cup}$ decides $L_1 \cup L_2$ in polynomial time, and hence $L_1 \cup L_2 \in \mathrm{P}$. [guided] We must build an actual polynomial-time decider for $L_1 \cup L_2$. The natural machine is the deterministic Turing machine $M_{\cup}$ that, on input $w \in \Sigma^*$, runs the known decider $M_1$ on $w$, runs the known decider $M_2$ on $w$, and then accepts exactly when at least one of the two simulations accepts. First we verify that this machine is a decider. Since $M_1$ halts on every input and $M_2$ halts on every input, the two simulations both terminate for every $w \in \Sigma^*$. After the two simulations finish, $M_{\cup}$ performs only a fixed finite amount of work to inspect the two answers and choose accept or reject. Thus $M_{\cup}$ halts on every input. Next we verify the running-time bound. If $|w| = n$, the first simulation takes at most $p_1(n)$ steps and the second takes at most $p_2(n)$ steps. The final Boolean check contributes a fixed constant number of steps, which is bounded by the constant $c_0$ chosen above. Therefore the total running time is bounded by \begin{align*} p_1(n) + p_2(n) + c_0 = q(n). \end{align*} Since $q$ is polynomial, $M_{\cup}$ runs in polynomial time. Finally we verify that $M_{\cup}$ decides the correct language. For every $w \in \Sigma^*$, \begin{align*} M_{\cup} \text{ accepts } w \iff M_1 \text{ accepts } w \text{ or } M_2 \text{ accepts } w. \end{align*} The definitions of $M_1$ and $M_2$ give \begin{align*} M_1 \text{ accepts } w \iff w \in L_1 \end{align*} and \begin{align*} M_2 \text{ accepts } w \iff w \in L_2. \end{align*} Substituting these equivalences, we obtain \begin{align*} M_{\cup} \text{ accepts } w \iff w \in L_1 \text{ or } w \in L_2. \end{align*} This is precisely the condition $w \in L_1 \cup L_2$. Therefore $M_{\cup}$ is a polynomial-time decider for $L_1 \cup L_2$. [/guided] [/step] [step:Decide the intersection by accepting when both deciders accept] Define a deterministic Turing machine $M_{\cap}$ as follows. On input $w \in \Sigma^*$, first run $M_1$ on $w$, then run $M_2$ on $w$. Accept if both computations accept, and reject otherwise. For every $w \in \Sigma^*$, both simulations halt, so $M_{\cap}$ halts. Its running time is at most \begin{align*} p_1(|w|) + p_2(|w|) + c_0 = q(|w|) \end{align*} steps, since $c_0$ was chosen to cover the fixed overhead for either Boolean operation. Moreover, \begin{align*} M_{\cap} \text{ accepts } w \iff M_1 \text{ accepts } w \text{ and } M_2 \text{ accepts } w. \end{align*} By the defining properties of $M_1$ and $M_2$, this is equivalent to \begin{align*} w \in L_1 \text{ and } w \in L_2. \end{align*} Hence $M_{\cap}$ decides $L_1 \cap L_2$ in polynomial time, so $L_1 \cap L_2 \in \mathrm{P}$. [/step] [step:Decide the complement by reversing the answer of the first decider] Define a deterministic Turing machine $M_{\mathrm{comp}}$ as follows. On input $w \in \Sigma^*$, run $M_1$ on $w$. If $M_1$ accepts, then reject; if $M_1$ rejects, then accept. Because $M_1$ is a decider, it halts on every input $w \in \Sigma^*$, so $M_{\mathrm{comp}}$ also halts on every input. Its running time is at most \begin{align*} p_1(|w|) + c_1 = r(|w|) \end{align*} steps, where $c_1$ is the fixed overhead for reversing the answer of $M_1$. Since $r$ is polynomial, $M_{\mathrm{comp}}$ runs in polynomial time. For every $w \in \Sigma^*$, \begin{align*} M_{\mathrm{comp}} \text{ accepts } w \iff M_1 \text{ rejects } w. \end{align*} Since $M_1$ decides $L_1$, the statement that $M_1$ rejects $w$ is equivalent to $w \notin L_1$. Therefore \begin{align*} M_{\mathrm{comp}} \text{ accepts } w \iff w \in \Sigma^* \setminus L_1. \end{align*} Thus $M_{\mathrm{comp}}$ decides $\Sigma^* \setminus L_1$ in polynomial time, and $\Sigma^* \setminus L_1 \in \mathrm{P}$. [/step] [step:Collect the three constructions] We have constructed deterministic polynomial-time deciders for $L_1 \cup L_2$, for $L_1 \cap L_2$, and for $\Sigma^* \setminus L_1$. By the definition of the class $\mathrm{P}$, these three languages all belong to $\mathrm{P}$. This proves the claimed Boolean closure properties. [/step]