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