05 Closure of P under Boolean combinations

Theorem

Suppose $L_{1}, L_{2} \in P$ . Then also:

$L_{1}^{c} = {x \in / L_{1}} \in P$

$L_{1} \cup L_{2} \in P$

$L_{1} \cap L_{2} \in P$

Let $A_{1} (x), A_{2} (x)$ be algorithms deciding $L_{1}, L_{2}$ respectively in polytime. $O (n^{k}) O (n_{1}^{k}), O (n_{2}^{k})$ $k = max (k_{1}, k_{2})$

Proof of $L_{1}^{c} = {x \in / L_{1}} \in P$

Run $A_{1} (x)$ and
- if accepts, reject
- if rejects, accept
This takes as much time as $A_{1} (x)$ plus an extra step, so its still $O (n_{1}^{k})$
This a new algorithm deciding $L_{1}^{c}$ in time $O (n_{1}^{k})$

Proof of $L_{1} \cup L_{2} \in P$

Run $A_{1} (x)$ and
- if accepts accept
- if rejects, run $A_{2} (x)$
  - if accepts, accept
  - if rejects, reject
This takes $O (n^{k}) O (n_{1}^{k}) + O (n_{2}^{k})$
This a new algorithm deciding $L_{1} \cup L_{2} \in P$ in time $O (n_{1}^{k}) + O (n_{2}^{k}) = O (n^{k})$

📝 My Obisidan Notes

Explorer

05 Closure of P under Boolean combinations

Proof of $L_{1}^{c} = {x \in / L_{1}} \in P$

Proof of $L_{1} \cup L_{2} \in P$

Graph View

Table of Contents

Backlinks

📝 My Obisidan Notes

Explorer

05 Closure of P under Boolean combinations

Proof of L1c​={x∈/L1​}∈P

Proof of L1​∪L2​∈P

Graph View

Table of Contents

Backlinks

Proof of $L_{1}^{c} = {x \in / L_{1}} \in P$

Proof of $L_{1} \cup L_{2} \in P$