Subconjunto suma vs subconjunto producto (dureza NP fuerte vs débil)

Esperaba que alguien pudiera explicarme por qué exactamente el problema del producto del subconjunto es fuertemente NP-duro, mientras que el problema de la suma del subconjunto es débilmente NP-duro.

Subconjunto Suma: Dada y , ¿existe un subconjunto tal que . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\sum_{i\in X'}x_i = T$

Subconjunto del producto: Dada y , ¿existe un subconjunto tal que . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\prod_{i\in X'}x_i = T$

Siempre pensé que los dos problemas eran equivalentes: una instancia de SS podría transformarse en una instancia de SP mediante exponenciación y una instancia de SP a SS mediante logaritmos. Esto me llevó a concluir que ambos pertenecían a la misma clase de NP-hard, es decir, ambos eran débilmente NP-hard.

Además, parece que la misma recurrencia podría usarse para resolver ambos problemas usando la programación dinámica con un cambio muy pequeño (reemplazando la resta en SS con la división en SP).

Eso fue hasta que leí el capítulo 8 de "Teoría de la computación" de Bernard Moret (para aquellos que no tienen el libro, tiene una prueba de la dureza del producto del subconjunto a través de X3C, un problema fuertemente NP-duro).

Entiendo la reducción, pero no puedo entender qué estaba mal con mi conclusión anterior (equivalencia de los dos problemas).

ACTUALIZACIÓN : Resulta que el producto del subconjunto solo es débilmente NP-completo (el producto objetivo es exponencial en ). Gary y Johnson publicaron esto en su columna de completitud NP en 1981 , pero supongo que era menos visible que su reclamo anterior en su libro. $\Omega (n)$

cc.complexity-theory np-hardness reductions subset-sum RDN
fuente

Probablemente sería bueno imaginar cómo implementaría su algoritmo de programación dinámica. Entonces, encontrarías lo que estaba mal.

Yoshio Okamoto

@ MohammadAl-Turkistany: Está en la sección final de esta columna

RDN

Respuestas:

Con respecto al problema de equivalencia de Subset Sum y Subset Product Hay un tecnicismo con respecto a Subset Product. ¡El producto de x's = T es en realidad Psuedopolynomial si T no es exponencial! Por lo tanto, las pruebas de que el producto del subconjunto es NP Hard no son (¡por razones técnicas!) ¡Bastante correctas!

Sin embargo, dada la promesa de que T es grande. ¡Entonces la reducción a través de Logaritmos a Subset Sum da una SUMA DE SUBSET NO ESTÁNDAR que supera los reales! Esto significa que el algoritmo Psuedopolynomial para Subset Sum no se aplica. Aunque los logaritmos son pequeños, ¡los lugares decimales estropean la programación dinámica psuedopolinómica!

espero que esto ayude

Zelah

Zelah 02
fuente

Resulta que siempre estuvo en lo correcto acerca de que las reducciones son incorrectas (es decir, afirman que muestran una completa integridad de NP, cuando no lo hacen). ¡Gracias!

RDN

En primer lugar, usar la exponenciación para pasar de SS a SP funciona (usando la base 2 en lugar de la base ), pero explota el tamaño de los números involucrados. Una dureza NP débil significa que si los números son pequeños (o más precisamente, indicados en unario), el problema ya no es difícil. Por lo tanto, el uso de la exponenciación crea instancias de SP de tamaño exponencial incluso para las instancias fáciles de SS, donde los números se escriben en unario. $e$

En segundo lugar, el uso de logaritmos para pasar de SP a SS no funciona, ya que los logaritmos generalmente generan valores no enteros. SS y SP se definen usando números enteros, y los logaritmos a menudo resultan en valores trascendentales, que son difíciles de representar o hacer cálculos matemáticos.

<edit>

Sea un número entero, , luego es racional si y solo si es una potencia de 2, y trascendental en caso contrario. En primer lugar, si $A$ $A > 0$ $\log_2 A$ $A$ para enteros distintos de ceroy, entonces $\log_2 A = \frac{p}{q}$ $p$ $q$ ,. Por lo tanto, tenemos quepor descomposición primaria. Además,, por lo tanto, dada una, podemos elegirypara demostrar quees racional. $A = 2^{\frac{p}{q}}$ $A^q = 2^p$ $A = 2^r$ $A^{rq} = 2^p$ $A$ $q=1$ $p=r$ $\log_2 A$

Solo tenemos que mostrar que nunca es trascendental de lo contrario. Esto se desprende del teorema de Gelfond-Schneider , para una formulación equivalente (como se puede encontrar en la página Wiki) es "si y son números algebraicos distintos de cero, y tomamos cualquier logaritmo no de , entonces es racional o trascendental ". También es fácil de verificar tomando el inverso del teorema y estableciendo y, por lo tanto, $\log_2 A$ $\alpha$ $\gamma$ $\alpha$ $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ $\alpha^\beta = \gamma$ . $\beta = \log_\alpha \gamma$

</edit>

Por último, considere lo que sucede cuando probamos el algoritmo de programación dinámica de SS en SP. Debido a que usamos productos en lugar de sumas, los números involucrados aumentan enormemente, y la precisión matemática arbitraria requerida de repente se convierte en un factor en el tiempo de ejecución. Es por eso que el algoritmo no puede resolver instancias de SP rápidamente, incluso si los números están en unario.

Alex ten Brink
fuente

Esto lleva a un caso especial algo interesante. ¿para qué clase de números los registros se pueden expresar como racionales y no requieren precisión infinita? en este caso, los problemas serían casi equivalentes y reducibles entre sí. También parece conducir a un algoritmo de aproximación "natural".

vzn

¡Gracias por la gran respuesta! Solo tengo un problema: entiendo por qué tomar registros es ilegal (excepto tal vez en el caso de que los registros tengan una longitud polivinílica, como señala vzn), pero todavía no estoy seguro de la legalidad de pasar de SS a SP por exponenciación. WRT va de SS a SP como mencionó (por exponenciación), no nos encontramos con el siguiente problema: el número de bits en la instancia de entrada de

y el número de bits en el instancia de

. Esta es una explosión exponencial. Entonces, ¿sigue siendo legal? Si es así, ¿por qué?

I_{S S}

$I_{SS}$

O (n \log x)

$O(n\log x)$

I_{S P}

$I_{SP}$

O (n x)

$O(nx)$

RDN

@vzn, RDN: edité una caracterización cuando el logaritmo es trascendental. Sobre la explosión en la reducción, depende de su definición de "legal": la reducción es correcta , pero su eficiencia no es polinómica, y por lo tanto no dice nada sobre la dureza NP. Por lo tanto , no es una reducción correcta de poli-tiempo , pero es una reducción correcta (sin calificadores).

Alex ten Brink

También hay un caso especial donde todos los números tienen la forma

, cada

racional, para cualquier

, no solo

. el algoritmo de aproximación en el que estaba pensando podría encontrar una

tal que la conversión de valores en esa "base" esté "cerca" de los originales.

c^{n_{i}}

$c^{n_i}$

n_{i}

$n_i$

c

$c$

c = 2

$c=2$

c

$c$

vzn

La explicación literal es que el problema del Producto del subconjunto es NP completo por una reducción de un problema fuertemente NP completo, como la cobertura exacta por 3 juegos. En tal reducción "fuerte", los enteros de entrada están delimitados por alguna función polinómica en el número de enteros en la instancia resultante del problema del Subconjunto de productos.

Tal reducción "fuerte" es imposible de cualquier problema fuertemente NP-completa a Subset Sum problema a menos que . Tenemos un algoritmo de programación dinámica de tiempo polinómico para resolver el problema de la suma de subconjuntos si los enteros de entrada están limitados por un polinomio. $P=NP$

Mohammad Al-Turkistany
fuente

Sí, lo entiendo. Mi pregunta era por qué la conclusión que había hecho antes era incorrecta (es decir, equivalencia de SS y SP).

RDN

@rdn No hay equivalentes en ese sentido a menos que P = NP.

Mohammad Al-Turkistany

Sí, entiendo eso. Pero quiero saber qué estaba mal con mis reducciones en cualquier dirección.

RDN

¿Puedes delinear tus reducciones?

Mohammad Al-Turkistany

I (S S) = ⟨ X, S ⟩

$I(SS)=\langle X, S \rangle$

I (S P) = ⟨ Y, P ⟩

$I(SP)=\langle Y, P \rangle$

I (S S)

$I(SS)$

I (S P)

$I(SP)$

P = e^{S}

$P = e^S$

Y_{i} = e^{X_{i}}

$Y_i = e^{X_i}$

S

$S$

P = e^{S}

$P = e^S$

I (S P)

$I(SP)$

I (S S)

$I(SS)$

S = l o g (P)

$S = log(P)$

X_{i} = \log (Y_{i})

$X_i = \log(Y_i)$

P

$P$

S = \log (P)

$S = \log(P)$