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
scroll top