es suficiente solo reduccion a problema NP-hard ?

IIC2213 / Syllabus-2021-1-

19 stars 2 forks source link

es suficiente solo reduccion a problema NP-hard ? #71

Open michimalonko opened 3 years ago

michimalonko commented 3 years ago

Tengo la duda si es suficiente encontrar una reduccion de los conjuntos oscuros a un problema NP-hard para solucionar el problema. o es necesario otro paso?

juanreutter commented 3 years ago

Mira los videos y las notas para asegurarte que tienes la dirección correcta con tu reducción. Si quieres mostrar que CO es NP-hard, debes reducir desde un problema NP-hard. Lo otro es mostrar también que el problema está en NP, como lo hicimos en clases y en ayudantía.