Proof for P-complete is not closed under intersection Unfortunately I have no idea how to show this:


  Show that the set of ${\sf P}$-complete languages is not closed under intersection.


As far as I understand my lecture notes, ${\sf P}$-completeness is defined as follows:


$A \subset \Sigma^{*}$ is complete for ${\sf P}$ iff $A \in \text{P}$ and $\forall B \in {\sf P}, B \le_L A$
$\le_L$ is ${\sf LOGSPACE}$-reduction: for $A,B \subset \Sigma^{*}$, the relation $A \le_{L} B$ is defined by
$$A \le_{L} B \quad\text{iff}\quad \exists f \in {\sf FLOGSPACE}, (x \in A \Leftrightarrow f(x) \in B)$$
Let $A$ be any P-complete problem (say circuit evaluation). Here are two other P-complete problems: $A_0 = \{0x : x \in A \}$ and $A_1 = \{1x : x \in A\}$. The problem $A_0 \cap A_1 = \emptyset$, while definitely in P, isn't P-complete. The latter is true even if we allow Turing reductions, assuming $L \neq P$.