1
$\begingroup$

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 Answers 1

1

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.

  • 0
    @XavierLabouze: Requiring the intersection to be nonempty does not make any essential difference. Please think about it.2011-10-07