[ Foro de Pseudocódigo ]

NP-completitud

04-Jul-2022 11:48
Invitado (Jorge)
0 Respuestas

Hola buenas, tengo dudas de la solución de este tipo de ejercicios NP-completitud, si alguien me pudiera dar una solución detallada con los pasos se lo agradecería.
El enunciado del ejercicio es:

Dado un conjunto U de objetos, una familia S={S1,...,Sn} de subconjuntos de U y un numero k, el problema SET-COVER consiste en determinar si existe una subfamilia T ? S de a lo sumo k subconjuntos cuya unión es igual a U. Demostrar que el problema SET-COVER es NP-completo utilizando el problema de decisión de la cobertura de vértices PDCV.




Si ya eres usuario del sistema, puedes contestar desde tu cuenta y así ganar prestigio.

Si sólo eres un visitante, puedes optar por...