# 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)$$
• This is the reason for quotation. I've searched in the literature (Papadimitriou, Bovet Crescenzi) and also on the internet, but I didn't find something useful. That's why I'm asking for help. Nov 29, 2012 at 12:56
• What reductions are you using? Might they be log-space many-to-one reductions (the reduction model favoured e.g. in Papadimitriou's text)? Nov 29, 2012 at 13:53
• Please accept my apologies for not providing the definition. I thought the definition is uniform. Here it is: $A \subset \Sigma^{*}$ is complete for $\text{P}$ if 1. $A \in \text{P}$ 2. $B \le_L A$ for all $B \in \text{P}$ Nov 29, 2012 at 14:14
• It all depends on the definition of $\le_L$. How is the reduction defined? Nov 29, 2012 at 17:07
• @A.Schulz: These lecture notes are a bit unstructured, but I think the definition above refers to the definition of the $\text{LOGSPACE}$-reduction: Let $A,B \subset \Sigma^{*}. A \le_{L} B: \Leftrightarrow \exists f \in \text{FLOGSPACE}$ with $(x \in A \Leftrightarrow f(x) \in B).$ Nov 29, 2012 at 17:22

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$.

• @A.Schulz: Concerning this answer I have to questions to you or Yuval: 1.) What could be an example for $x$? 2.) I understand why $A_0 \cap A_1 = \emptyset$, but how do I see that this is in $P$? Dec 4, 2012 at 15:40

I think this questions exploits only a technicality. However, you can follow this path

1. The class of ${\sf P}$-complete languages does not contain $\Sigma^*$ and $\emptyset$. This is true for all classes and not only ${\sf P}$, since in order to reduce a language $L_1\neq\emptyset,\Sigma^*$ to another language $L_2$, there has to be at least one element in $L_2$ and at least one element in $\bar L_2$
2. Show that there are two disjoint ${\sf P}$-complete languages (use Yuval's answer).
• This depends on what reduction-class is being considered. Because $\mathsf P$-completeness is somewhat trivial under polynomial-time many-to-one reductions, I would assume for that very reason that he was considering something like log-space many-to-one reductions, in which case if is not known whether $\mathsf L$ is a subset of the $\mathsf P$-complete problems. Nov 29, 2012 at 13:52
• @NieldeBeaudrap: You are right. However, if somebody talks about reduction and the class ${\sf P}$ I usually would expect polytime many-one reductions as the standard reduction. My answer, on the other hand, holds for all many-one reductions, since $\emptyset$ can never be (many-one) complete due to technical reasons. Nov 29, 2012 at 14:10
• As we don't know whether $\mathsf L \ne \mathsf P$, I would say that precisely if $\mathsf P$ is involved, you should ask about whether a stronger notion of reduction is being used. Anyhow, the second part of your answer certainly is true; I just think that you should soften the first part to note that, whether or not "$\mathsf P$-complete = $\mathsf P \smallsetminus \{\Sigma^\ast, \varnothing\}$", it is certainly true that $\varnothing$ is not $\mathsf P$-complete (as this is actually all that your answer requires). Nov 29, 2012 at 15:56
• @A.Schulz: Thank you for your answer, Professor Schulz. Concerning your first aspect: I've provided our definition of $\text{P}$-complete above and as far as I can tell, although it excludes $\Sigma^*$, it doesn't exclude $\emptyset$. So our definition is wrong, isn't it? Concerning your second aspect: I think the answer provided later on by Yuval is that what you meant? Nov 29, 2012 at 15:59
• @Uriel: I extended my answer. Dec 4, 2012 at 12:04