Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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