# Reduction over intersection of languages

Given two languages $L1$ and $L2$, such that $L2$ is NP-Hard under polytime (many-one or Turing) reduction. Let $L=L1\cap L2$.

1- Is it true that if $L2$ is polytime (many-one or Turing) reducible to a third language $L3$, then $L$ is polytime reducible to $L1\cap L3$ ?

2- If $L \in$ P, what can it be concluded about the complexity of $L1$ ?

-

1: No. For example, let X be an EXP-hard language, and let L=L1=L2={0x: xX} and L3={1x: xX}. Then,

• Both L and L2 are EXP-hard. In particular, L does not belong to P and L2 is NP-hard.
• L2 is polynomial-time many-one reducible to L3.
• L1L3 is the empty set. Because L∉P, this implies that L is not polynomial-time Turing reducible to L1L3.

2: Nothing. Let X be an arbitrary language and Y be an NP-hard language. Let L1={0x: xX} and L2={1y: yY}. Although L1L2 is the empty set and therefore trivially belongs to P, and L2 is indeed NP-hard, this does not tell anything about the complexity of L1.

-
Right, I should have precised : in case of non-empty intersections. – Xavier Labouze Oct 7 '11 at 13:54
@XavierLabouze: Requiring the intersection to be nonempty does not make any essential difference. Please think about it. – Tsuyoshi Ito Oct 7 '11 at 13:57
I see, thank you. – Xavier Labouze Oct 7 '11 at 16:39
If you like his answer, please consider to up vote it and accept it. – sxd Nov 7 '11 at 0:09