# For any non-trivial $A,B$, finding a language which both are polynomially reducible to

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.

• 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? – fade2black Jul 2 '17 at 11:17
• 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?) – Nescio Jul 2 '17 at 11:20
• Take 0A+1B as your C. – Yuval Filmus Jul 2 '17 at 11:24
• Your proof for c) is correct. For a) please see YuvalFilmus' comment. – fade2black Jul 2 '17 at 13:05

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.