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$ ?

Thank you for your answers.


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.

  • $\begingroup$ Right, I should have precised : in case of non-empty intersections. $\endgroup$ – Xavier Labouze Oct 7 '11 at 13:54
  • $\begingroup$ @XavierLabouze: Requiring the intersection to be nonempty does not make any essential difference. Please think about it. $\endgroup$ – Tsuyoshi Ito Oct 7 '11 at 13:57

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.