LISTA DE PROBLEMAS

problema de la suma de subconjuntos es un problema de decisión importante en la teoría de la complejidad y la criptografía . Hay varias formulaciones equivalentes del problema. Uno de ellos es: dado un conjunto (o conjunto múltiple ) de enteros, ¿hay un subconjunto no vacío cuya suma es cero? Por ejemplo, dado el conjunto$${\ displaystyle \ {- 7, -3, -2,5,8 \}}, la respuesta es sí porque el subconjunto$${\ displaystyle \ {- 3, -2,5 \}}sumas a cero. El problema es NP-completo , lo que significa aproximadamente que, si bien es fácil confirmar si una solución propuesta es válida, puede ser inherentemente difícil determinar en primer lugar si existe alguna solución.

El problema puede formularse de manera equivalente como: dados los números enteros o naturales $${\ displaystyle w_ {1}, \ ldots, w_ {n}} ¿algún subconjunto de ellos suma precisamente $${\ displaystyle W}? ^{[1] La} suma de subconjuntos también puede considerarse como un caso especial del problema de la mochila . ^[2] Un caso especial interesante de suma de subconjuntos es el problema de partición , en el que$${\ displaystyle W} es la mitad de la suma de todos los elementos del conjunto (es decir, $${\ displaystyle W = {\ frac {1} {2}} (w_ {1} + \ dots + w_ {n})})

Complejidad [ editar ]

La complejidad del problema de la suma de subconjuntos se puede ver como dependiente de dos parámetros, N , el número de variables de decisión y P , la precisión del problema (indicado como el número de valores de posición binarios que se necesitan para establecer el problema). (Nota: aquí las letras N y P significan algo diferente de lo que significan en la clase de problemas NP ).

La complejidad de los algoritmos mejor conocidos es exponencial en el menor de los dos parámetros N y P . Por lo tanto, el problema es más difícil si N y P son del mismo orden. Solo se vuelve fácil si N o P se vuelven muy pequeños.

Si N (el número de variables) es pequeño, entonces una búsqueda exhaustiva de la solución es práctica. Si P (el número de valores de posición) es un número fijo pequeño, entonces hay algoritmos de programación dinámica que pueden resolverlo exactamente.

A continuación se proporcionan algoritmos eficientes para casos de N pequeña y P pequeña .

Algoritmo de tiempo exponencial [ editar ]

Hay varias formas de resolver la suma de subconjuntos en tiempo exponencial en $${\ displaystyle n}. El algoritmo más ingenuo sería recorrer todos los subconjuntos de$${\ displaystyle n}números y, para cada uno de ellos, verifique si el subconjunto suma al número correcto. El tiempo de ejecución es de orden.$${\ displaystyle O (2 ^ {n} n)}, puesto que hay $${\ displaystyle 2 ^ {n}} subconjuntos y, para verificar cada subconjunto, necesitamos sumar como máximo $${\ displaystyle n} elementos.

Se conoce un mejor algoritmo de tiempo exponencial que se ejecuta en el tiempo O (2 ^{N / 2} ). El algoritmo divide arbitrariamente los N elementos en dos conjuntos de N / 2 cada uno. Para cada uno de estos dos conjuntos, almacena una lista de las sumas de todos los 2 ^{N / 2} subconjuntos posibles de sus elementos. Cada una de estas dos listas se ordena. El uso de un algoritmo de clasificación de comparación estándar para este paso llevaría tiempo O (2 ^{N / 2} N ). Sin embargo, dada una lista ordenada de sumas para k elementos, la lista puede expandirse a dos listas ordenadas con la introducción de a ( k + 1) elemento st, y estas dos listas ordenadas se pueden combinar en el tiempo O (2 ^k ). Por lo tanto, cada lista se puede generar en forma ordenada en el tiempo O (2 ^{N / 2} ). Dadas las dos listas ordenadas, el algoritmo puede verificar si un elemento de la primera matriz y un elemento de la segunda matriz suman s en el tiempo O (2 ^{N / 2} ). Para hacer eso, el algoritmo pasa a través de la primera matriz en orden decreciente (comenzando en el elemento más grande) y la segunda matriz en orden creciente (comenzando en el elemento más pequeño). Siempre que la suma del elemento actual en la primera matriz y el elemento actual en la segunda matriz sea mayor que s, el algoritmo se mueve al siguiente elemento en la primera matriz. Si es menor que s , el algoritmo se mueve al siguiente elemento en la segunda matriz. Si se encuentran dos elementos con suma s , se detiene. Horowitz y Sahni publicaron este algoritmo por primera vez en un informe técnico en 1974. ^[3]

Solución de programación dinámica de tiempo pseudo-polinomial [ editar ]

El problema se puede resolver en tiempo pseudo-polinomial usando programación dinámica . Supongamos que la secuencia es

x ₁ , ..., x _N

ordenados en orden creciente y deseamos determinar si hay un subconjunto no vacío que sume a cero. Defina la función de valor booleano Q ( i , s ) como el valor ( verdadero o falso ) de

"hay un subconjunto no vacío de x ₁ , ..., x _i que suma a s ".

Por lo tanto, la solución al problema "Dado un conjunto de enteros, ¿hay un subconjunto no vacío cuya suma es cero?" es el valor de Q ( N , 0).

Sea A la suma de los valores negativos y B la suma de los valores positivos. Claramente, Q ( i , s ) = falso , si s < A o s > B . Por lo tanto, estos valores no necesitan ser almacenados o calculados.

Crear una matriz para contener los valores Q ( i , s ) para 1 ≤ i ≤ N y A ≤ s ≤ B .

El conjunto ahora se puede completar utilizando una recursión simple. Inicialmente, para A ≤ s ≤ B , establezca

Q (1, s ): = ( x ₁ == s )

donde == es una función booleana que devuelve verdadero si x ₁ es igual a s , de lo contrario, falso.

Entonces, para i = 2, ..., N , establece

Q ( i , s ): = Q ( i - 1, s ) o ( x _i == s ) o Q ( i - 1, s - x _i ), para A ≤ s ≤ B .

Para cada asignación, los valores de Q en el lado derecho ya son conocidos, ya sea porque se almacenaron en la tabla para el valor anterior de i o porque Q ( i - 1, s - x _i ) = falso si s - x _i < A o s - x _i > B . Por lo tanto, el número total de operaciones aritméticas es O ( N ( B - A )). Por ejemplo, si todos los valores son O( N ^k ) para algunos k , entonces el tiempo requerido es O ( N ^k +2 ).

Este algoritmo se modifica fácilmente para devolver el subconjunto con suma 0 si hay uno.

La solución de programación dinámica tiene un tiempo de ejecución de $${\ displaystyle O (sN)} dónde $${\ displaystyle s} es la suma que queremos encontrar en un conjunto de $${\ displaystyle N}números. Esta solución no cuenta como tiempo polinómico en la teoría de la complejidad porque B - A no es polinomial en el tamaño del problema, que es el número de bits utilizados para representarlo. Este algoritmo es polinómico en los valores de A y B , que son exponenciales en su número de bits.

Para el caso de que cada x _i es positiva y limitada por una constante fija C , Pisinger encontró un algoritmo de tiempo lineal que tiene tiempo complejidad O ( NC ) (nota que esto es para la versión del problema donde la suma de destino no es necesariamente cero, de lo contrario, el problema sería trivial). ^[4] En 2015, Koiliaris y Xu encontraron un determinista$${\ displaystyle {\ tilde {O}} (s {\ sqrt {N}})} algoritmo para el problema de suma de subconjuntos donde $${\ displaystyle s}es la suma que necesitamos encontrar. ^[5] En 2017, Bringmann encontró un estudio aleatorizado$${\ displaystyle {\ tilde {O}} (s)}algoritmo de tiempo ^[6] .

Algoritmo aproximado de tiempo polinómico [ editar ]

Una versión aproximada de la suma del subconjunto sería: dado un conjunto de N números x ₁ , x ₂ , ..., x _N y un número s , salida

• sí, si hay un subconjunto que suma s ;
• no, si no hay un subconjunto que suman un número entre (1 - c ) es y es por alguna pequeña c > 0;
• ninguna respuesta, si hay un subconjunto que suman un número entre (1 - c ) s y s , pero ningún subconjunto que suman s .

Si todos los números no son negativos, la suma aproximada del subconjunto se puede resolver en el polinomio temporal en N y 1 / c .

La solución para la suma de subconjuntos también proporciona la solución para el problema de suma de subconjuntos original en el caso de que los números sean pequeños (de nuevo, para números no negativos). Si se puede especificar una suma de los números con como máximo P bits, entonces resolver el problema aproximadamente con c = 2 ^- P es equivalente a resolverlo exactamente. Luego, el algoritmo de tiempo polinomial para la suma aproximada del subconjunto se convierte en un algoritmo exacto con polinomio de tiempo de ejecución en N y 2 ^P (es decir, exponencial en P ).

El algoritmo para el problema aproximado de la suma de subconjuntos es el siguiente:

Inicializar una lista S para contener un elemento 0.

para cada  i de 1 a N  , 
    deje que T sea ​​una lista que consiste en x i + y , para todo y en S, 
    sea U la unión de T y S, el 
    tipo U 
    hace que S esté vacío
    vamos y ser el elemento más pequeño de T  
    agregan y al S 
    para cada elemento z de U creciente Do
        // Recorte la lista eliminando números cercanos entre sí
        // y arrojar elementos mayores que s .
        si  y + cs / N < z ≤ s  entonces 
            y = z 
            agregue z a S

si  S contiene un número entre (1 - c ) es  e  s  a continuación, 
    volver sí 
demás 
    retorno sin

El algoritmo es el tiempo polinomial porque las listas S , T y U siempre permanecen de tamaño polinomial en N y 1 / c y, siempre que sean de tamaño polinomial, todas las operaciones en ellas se pueden realizar en tiempo polinomial. El tamaño de las listas se mantiene polinomial mediante el paso de recorte, en el que solo incluimos un número z en S si es mayor que el anterior por cs / N y no mayor que s .

Este paso asegura que cada elemento en S es más pequeño que el siguiente en al menos cs / N y no contiene elementos mayores que s . Cualquier lista con esa propiedad consta de no más de N / c elementos.

El algoritmo es correcto porque cada paso introduce un error aditivo de como máximo cs / N y N pasos juntos introducen el error de como máximo cs .

cadena más cercana es un problema computacional NP-duro , ^[1] que trata de encontrar el centro geométrico de un conjunto de cadenas de entrada.

Para comprender la palabra "centro", es necesario definir una distancia entre dos cadenas. Por lo general, este problema se estudia teniendo en cuenta la distancia de Hamming .

Definición formal [ editar ]

Más formalmente, dada n longitud- m cadenas s ₁ , s ₂ , ..., s _n , el problema de cadena más cercano busca una nueva longitud- m cadena s tal que d ( s , s _i ) ≤ k para todo i , donde d denota la distancia de Hamming , y donde k es lo más pequeño posible. ^[2] Una versión de problema de decisión del problema de cadena más cercano, que es NP-complete , en su lugar tomak como otra entrada y pregunta si hay una cadena dentro de la distancia de Hamming k de todas las cadenas de entrada. ^[1]

El problema de la cadena más cercana puede verse como un caso especial del problema genérico de 1 centro en el que las distancias entre elementos se miden usando la distancia de Hamming.

Motivación [ editar ]

En bioinformática , el problema más cercano de las cuerdas es una faceta intensamente estudiada del problema de encontrar señales en el ADN .

Simplificaciones y reducciones de datos [ editar ]

Las instancias de la cadena más cercana pueden contener información que no es esencial para el problema. En cierto sentido, la entrada habitual de la cadena más cercana contiene información que no contribuye a la dureza del problema. Por ejemplo, si algunas cadenas contienen el carácter a , pero ninguna contiene el carácter z , reemplazar todas a s por z s produciría una instancia esencialmente equivalente, es decir: a partir de una solución de la instancia modificada, la solución original se puede restaurar, y viceversa.

Normalizando la entrada [ editar ]

Cuando todas las cadenas de entrada que comparten la misma longitud se escriben una encima de la otra, forman una matriz. Ciertos tipos de filas tienen esencialmente las mismas implicaciones para la solución. Por ejemplo, reemplazar una columna con entradas ( a , a , b ) con otra columna ( x , x , y ) podría conducir a una cadena de solución diferente, pero no puede afectar la capacidad de solución, porque ambas columnas expresan la misma estructura, a saber. Las dos primeras entradas son iguales, pero diferentes de la tercera.

Una instancia de entrada puede normalizarse reemplazando, en cada columna, el carácter que ocurre con mayor frecuencia con a , el carácter que ocurre con mayor frecuencia con b , y así sucesivamente. Dada una solución para la instancia normalizada, la instancia original se puede encontrar reasignando los caracteres de la solución a su versión original en cada columna.

El orden de las columnas no contribuye a la dureza del problema. Eso significa que, si permutamos todas las cadenas de entrada de acuerdo con cierta permutación π y obtenemos una cadena de solución s para esa instancia modificada, entonces π ⁻¹ ( s ) será una solución para la instancia original.

Ejemplo [ editar ]

Busca espacio para el problema normalizado. La cadena central aaaa y aaab conduce a las distancias de Hamming 1,2,1 y 2,1,1, respectivamente.

Dada una instancia con tres cadenas de entrada uvwx , xuwv y xvwu . Esto podría escribirse como una matriz como esta:

tu	v	w	X
X	tu	w	v
X	v	w	tu

La primera columna tiene los valores ( u , x , x ). Como x es el carácter que aparece con mayor frecuencia, lo reemplazamos por a , y reemplazamos u , el segundo carácter con mayor frecuencia, por b , obteniendo la nueva primera columna ( b , a , a ). La segunda columna tiene los valores ( v , u , v ). En cuanto a la primera columna, v se sustituye por una y u se sustituye por b , la obtención de la nueva segunda columna ( un , b, Un ). Hacer lo mismo con todas las columnas da la instancia normalizada

si	una	una	una
una	si	una	si
una	una	una	do

Reducción de datos obtenidos de la normalización [ editar ]

La normalización de la entrada reduce el tamaño del alfabeto a como máximo el número de cadenas de entrada. Esto puede ser útil para algoritmos cuyos tiempos de ejecución dependen del tamaño del alfabeto.

Aproximabilidad [ editar ]

Li y col. evolucionó un esquema de aproximación de tiempo polinómico ^[3] que es prácticamente inutilizable debido a las grandes constantes ocultas.

Trazabilidad de parámetros fijos [ editar ]

La cadena más cercana se puede resolver en $${\ displaystyle O (kL + kd \ cdot d ^ {d})}, donde k es el número de cadenas de entrada, L es la longitud de todas las cadenas yd es la distancia máxima deseada desde la cadena de solución a cualquier cadena de entrada. ^[4]

Relaciones con otros problemas [ editar ]

La cadena más cercana es un caso especial del problema de subcadena más cercano más general , que es estrictamente más difícil. Mientras que la cadena más cercana resulta ser manejable con parámetros fijos de varias maneras, la subcadena más cercana es W [1] -dura con respecto a estos parámetros.