Problema de igualdad de subconjuntos : Dado un conjunto S de valores enteros no negativos, el problema es identificar si hay una partición del conjunto S en dos conjuntos X e Y , tal que la suma de enteros en X es igual a la suma de enterosen Y.
Explicación :
una instancia del problema es una entrada especificada para el problema. Una instancia del problema de igualdad de subconjuntos es un conjunto S . Dado que un problema NP-Completo es un problema que está tanto en NP como en NP-difícil , la prueba de la afirmación de que un problema es NP-Completo consta de dos partes:
- El problema en sí está en la clase NP .
- Todos los demás problemas en la clase NP pueden ser reducibles en tiempo polinomial a eso. (B es reducible en tiempo polinomial a C se denota como B ≤ P C )
Si solo se cumple la segunda condición , el problema se llama NP-Hard .
Pero no es posible reducir cada problema NP a otro problema NP para mostrar su NP-Completitud todo el tiempo. Por lo tanto, para mostrar que un problema es NP-Completo, entonces prueba que el problema está en NP y cualquier problema NP-Completo es reducible a eso, es decir, si B es NP-Completo y B ≤ P C entonces para C en NP, entonces C es NP-Completo. Por lo tanto, se puede concluir que el problema de igualdad de subconjuntos es NP-Completo utilizando las siguientes dos proposiciones:
- La igualdad de subconjuntos está en NP
- La igualdad de subconjuntos es NP-Hard
Estas dos proposiciones se pueden probar ya que el problema de igualdad de subconjuntos es un caso especial del problema de suma de subconjuntos donde la suma de cada partición del subconjunto X e Y en S se puede establecer como:
Dado que la suma de subconjuntos es NP-Completa , el problema de igualdad de subconjuntos también se convierte en NP-Completa .
Publicación traducida automáticamente
Artículo escrito por yashchuahan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA