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$
4
  • $\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, 2017 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, 2017 at 11:20
  • $\begingroup$ Take 0A+1B as your C. $\endgroup$ Jul 2, 2017 at 11:24
  • $\begingroup$ Your proof for c) is correct. For a) please see YuvalFilmus' comment. $\endgroup$
    – fade2black
    Jul 2, 2017 at 13:05

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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