Do polynomial reduction functions work both ways?
-
03-11-2019 - |
Pregunta
For example to prove 3-Sat ≤p Independent Set do I just have to prove this theorem:
Theorem- Formula F is satisfiable IFF graph has an independent set.
If I have to prove it this way does this also mean that Independent Set ≤p 3-Sat as well since the theorem goes both ways?
No hay solución correcta
Licenciado bajo: CC-BY-SA con atribución
No afiliado a cs.stackexchange