[Tarea 5] Problemas de decision
Opened this issue · 2 comments
Hola, en los 21 problemas NP-completos de Karp en wikipedia, no todos presentan su problema de decisión, existe solo un problema de decisión o varios NP-completo por problema? Por ejemplo 3 CNF SAT, existe el problema de decisión si la formula es satisfacible. o también esta el problema de decisión si la formula es satisfacible con n proposiciones con valuación 1, como podemos utilizar estas variantes de problemas de decisión, o cual problema de decisión ocupar cuando el problema no entrega uno?
todo depende de como se define el problema. Pero mira si prefieres el paper original de Karp: https://cgi.di.uoa.gr/~sgk/teaching/grad/handouts/karp.pdf (el link está en la parte de referencias del artículo de wikipedia).
De cualquier forma, la tarea se puede hacer reduciendo desde problemas np-completos que vimos en clases o ayudantías, les dí la flexibilidad de usar esos otros por que quizá para alguno salía más fácil de otro problema. Tienes, si quieres, la flexibilidad de usar alguna otra definición (razonable) de problema de decisión asociado a algún problema de Karp si asi lo prefieres!
Vale gracias!