4
$\begingroup$

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)$$
Improve this question
$\endgroup$
5
  • $\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
    Commented Nov 29, 2012 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
    Commented Nov 29, 2012 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
    Commented Nov 29, 2012 at 14:14
  • $\begingroup$ It all depends on the definition of $\le_L$. How is the reduction defined? $\endgroup$
    – A.Schulz
    Commented Nov 29, 2012 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
    Commented Nov 29, 2012 at 17:22

2 Answers 2

Reset to default
10
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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
    Commented Dec 4, 2012 at 15:40
5
$\begingroup$

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).
Improve this answer
$\endgroup$
6
  • 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
    Commented Nov 29, 2012 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
    Commented Nov 29, 2012 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
    Commented Nov 29, 2012 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
    Commented Nov 29, 2012 at 15:59
  • 1
    $\begingroup$ @Uriel: I extended my answer. $\endgroup$
    – A.Schulz
    Commented Dec 4, 2012 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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