La suma del subconjunto es NP completo

Requisito previo: NP-Completitud , Problema de suma de subconjuntos

Problema de suma de subconjuntos: dados N enteros no negativos a ₁ …a _N y una suma objetivo K , la tarea es decidir si hay un subconjunto que tiene una suma igual a K .

Explicación: una instancia del problema es una entrada especificada para el problema. Una instancia del problema de la suma de subconjuntos es un conjunto S = {a ₁ , …, a _N } y un número entero K . 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. Es por eso que si queremos mostrar que un problema es NP-Completo, solo mostramos que el problema está en NP y cualquier problema NP-Completo es reducible a eso, entonces hemos terminado, es decir, si B es NP-Completo y B≤P ^C para C en NP, entonces C es NP-Completo. Por lo tanto, podemos verificar que el problema de la suma de subconjuntos es NP-Completo usando las siguientes dos proposiciones:

La suma del subconjunto está en NP:
si algún problema está en NP, entonces, dado un certificado, que es una solución al problema y una instancia del problema (un conjunto S de entero a ₁ … a _N y un entero K ) seremos capaz de identificar (si la solución es correcta o no) certificado en tiempo polinomial. Esto se puede hacer verificando que la suma de los números enteros en el subconjunto S’ sea igual a K .

Subset Sum es NP-Hard:
Para demostrar que Subset Sum es NP-Hard, realice una reducción de un problema NP-Hard conocido a este problema.
Realice una reducción a partir de la cual el problema de cobertura de vértices se reduzca al problema de suma de subconjuntos . Supongamos un gráfico G(V, E) donde V = {1, 2, …, N}. Ahora, para cada vértice i, a _i =i . Para cada arista (i, j) definimos un componente llamado b _ij .
Representaremos los números enteros en un formato de array, donde cada fila se expresa en la representación de base 4 del valor entero correspondiente de |E|+1 dígitos.
La array tiene las siguientes propiedades:

La primera columna contiene un valor entero 1 para ai _y 0 _para bij .
Cada una de las columnas E que comienzan en el lado derecho de la array representa un dígito para cada borde. La columna (i, j)=1 para a _i , a _j y b _ij , en caso contrario, es igual a 0.
Definimos una constante k’ tal que,

$k' = k(4^{|E|}) + \sum _{i=0}^{|E|-1}2(4^{i})$

Ahora bien, se cumplen las siguientes proposiciones:

Consideremos un subconjunto de vértices y aristas a (V’, E’) respectivamente, tal que

$\sum _{i\epsilon V'}a_{i} + \sum _{(i, j)\epsilon E'}b_{ij} = k'$

b _ij puede contener como máximo 1 en cada columna. Además, el parámetro k’ tiene un 2 en todos los dígitos menos significativos hasta |E|. Nunca podemos tener un equipaje de mano en estos dígitos. Ahora, estos dígitos suman como máximo tres 1 en cada columna. Esto implica que para cada arista (i, j), V’ debe contener i o j. Por lo tanto, V’ se convierte en una cubierta de vértices.

Supongamos que hay una cubierta de vértice de tamaño k, elegiremos números enteros _ai tales que i esté en V’ y todos los b ij _tales que i o j estén en V’. Al sumar todos estos enteros en representación de base 4 (que elegimos de la array), obtenemos suma de enteros =k’. Por lo tanto, los enteros elegidos forman el subconjunto de enteros con suma = k’. Por lo tanto, la suma del subconjunto se cumple.

Consideremos el siguiente ejemplo,
Dada una cubierta de vértice V = {1, 3} y k = 2

Ahora, un ₁ = 1, un ₂ = 2, un ₃ = 3, un ₄ = 4

La array se puede construir de la siguiente manera:

=> $k' = k(4^{4})+\sum _{i=0}^{3}2(4^{i})$

=> $k' = 2(4^{4})+2(4^{0})+2(4^{1})+2(4^{2})+2(4^{3})$

=> $k' = 2(256+1+4+16+64) = 682$

Ahora, para probar el valor de k’, elijamos a _i tal que i esté en V’, elijamos a ₁ y a ₃ y b _ij tal que i o j esté en V’, es decir, elijamos b _ij tal que i o j están en V’, es decir, elegimos b ₁₂ , b ₁₄ , b ₂₃ y b ₃₄ de la array . En representación base 4, tenemos los siguientes valores:

a ₁ = 321, a ₃ = 276, a ₁₂ = 64, a ₂₃ = 16, a ₁₄ = 1, a ₃₄ = 4

Estos valores se calculan utilizando la array. Al sumar estos valores, obtenemos,

k’ = 321 + 276 + 64 + 16 + 1 + 4 = 682.

Por lo tanto, el valor de k’ se puede calcular y verificar.

Problema de suma de subconjuntos

Publicación traducida automáticamente

Artículo escrito por yashchuahan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta