Si tengo dos lenguajes L1 y L2, donde L2 es NP-Hard, si existe una reducción NP de L1 a L2 entonces L1 también es NP-Hard?
Desde un punto de vista de complejidad me hace sentido, ya que si sabemos que L2 es del tipo mas difícil de resolver en NP, independiente de la reducción que se haga de L1 a L2, L1 va a ser a lo mas igual de difícil que L2.
Hola,
Si tengo dos lenguajes L1 y L2, donde L2 es NP-Hard, si existe una reducción NP de L1 a L2 entonces L1 también es NP-Hard?
Desde un punto de vista de complejidad me hace sentido, ya que si sabemos que L2 es del tipo mas difícil de resolver en NP, independiente de la reducción que se haga de L1 a L2, L1 va a ser a lo mas igual de difícil que L2.