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)$$
  • $\begingroup$ 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. $\endgroup$ – Uriel Nov 29 '12 at 12:56
  • $\begingroup$ What reductions are you using? Might they be log-space many-to-one reductions (the reduction model favoured e.g. in Papadimitriou's text)? $\endgroup$ – Niel de Beaudrap Nov 29 '12 at 13:53
  • $\begingroup$ 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}$ $\endgroup$ – Uriel Nov 29 '12 at 14:14
  • $\begingroup$ It all depends on the definition of $\le_L$. How is the reduction defined? $\endgroup$ – A.Schulz Nov 29 '12 at 17:07
  • $\begingroup$ @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).$ $\endgroup$ – Uriel Nov 29 '12 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$.

  • $\begingroup$ @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$? $\endgroup$ – Uriel Dec 4 '12 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).
  • 5
    $\begingroup$ 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. $\endgroup$ – Niel de Beaudrap Nov 29 '12 at 13:52
  • 1
    $\begingroup$ @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. $\endgroup$ – A.Schulz Nov 29 '12 at 14:10
  • $\begingroup$ 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). $\endgroup$ – Niel de Beaudrap Nov 29 '12 at 15:56
  • $\begingroup$ @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? $\endgroup$ – Uriel Nov 29 '12 at 15:59
  • 1
    $\begingroup$ @Uriel: I extended my answer. $\endgroup$ – A.Schulz Dec 4 '12 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.