1
$\begingroup$

Given two non-trivial (not $\emptyset$ or $\Sigma^*$) languages $A$, $B$ over an alphabet $\Sigma$, which of the following is correct:

a. There is a language $C$ such that $A\leq_pC$ and $B\leq_pC$.

[..]

c. There is a language $C$ such that $C\leq_pA$ and $C\leq_pB$.

According to two different sources I've seen the correct answer seems to be (a), which is exactly why I'm trying to understand two things:

  1. Why is (a) a correct answer? Taking two languages in $EXP$, for example, I do not see why it's obvious they are polynomially reducible to each other.

  2. Why is (c) not a correct answer? Taking a language $C\in P$ since $A$ and $B$ are not trivial there are some $a\in A, a'\notin A$ and $b\in B, b'\notin B$, and therefore given a polynomial TM $M$ deciding $C$ I can define a reduction $f$ to $A$ by $f(x)=a$ if $M(x)$ accepts and $f(x)=a'$ otherwise and similarly for $B$, so it seems to me that (c) is a correct answer.

$\endgroup$
  • $\begingroup$ Given what you posted I think both are true. Assume for a) $C=SAT$, $A,B$ are any languages in $P$. For c) $A,B$ are any NP complete languages, while $C$ is any language in $P$. Maybe there is additional constraint? $\endgroup$ – fade2black Jul 2 '17 at 11:17
  • $\begingroup$ There are particular examples that satisfy both (a) and (c), but is (a) true in general, for every two non-trivial languages $A$ and $B$? (and is my proof that (c) is true in general even correct?) $\endgroup$ – Nescio Jul 2 '17 at 11:20
  • $\begingroup$ Take 0A+1B as your C. $\endgroup$ – Yuval Filmus Jul 2 '17 at 11:24
  • $\begingroup$ Your proof for c) is correct. For a) please see YuvalFilmus' comment. $\endgroup$ – fade2black Jul 2 '17 at 13:05
2
$\begingroup$

Part (a) is correct since you can take the language $$ C = \{ 0x : x \in A \} \cup \{ 1y : y \in B \}. $$ Here $0x$ is the concatenation of the strings 0 and $x$. This part works even when $A,B$ are trivial.

Part (c) is correct by taking $C = \emptyset$ and using $A,B \neq \Sigma^*$, for example.

$\endgroup$

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.