¿El problema del "subconjunto de productos" es NP completo?

El problema de la suma de subconjuntos es un problema clásico de NP completo:

Dada una lista de números y un objetivo , ¿hay un subconjunto de números de $L$ $k$ $L$ que sume a ? $k$

Un estudiante me preguntó si esta variante del problema llamado problema del "subconjunto de productos" es NP-complete:

Dada una lista de números y un objetivo , ¿hay un subconjunto de números de cuyo producto es $L$ $k$ $L$ ? $k$

Hice un poco de búsqueda y no pude encontrar ningún recurso que hablara sobre este problema, aunque quizás los extrañé.

¿El problema del subconjunto de productos es NP-completo?

complexity-theory np-complete reductions templatetypedef
fuente

Respuestas interesantes, pero me pregunto: ¿no podemos reducir a Subset Sum simplemente tomando registros de k y todos los números? (¿Tal vez debería hacer una pregunta por separado?)

j_random_hacker

@j_random_hacker, sí, si no puede encontrar una respuesta después de buscar en este sitio y en línea, le sugiero que publique una pregunta por separado. Es una buena pregunta con una buena respuesta (pista: tomar registros te deja con algo que no es un número entero; en la otra dirección, piensa en lo que la exponenciación hace con el tamaño de los números), pero es un poco tangente y sería mejor en su propia pregunta.

@DW: ¡Gracias, cuando tenga tiempo haré lo que me sugieres!

j_random_hacker

Respuestas:

Un comentario menciona una reducción de X3C a PRODUCTO SUBSET atribuido a Yao. Dado el objetivo de la reducción, no fue difícil adivinar cuál era la reducción.

Definiciones:

CUBIERTA EXACTA POR 3-SETS (X3C)

Dado un conjunto finito con un múltiplo de 3, y una colección de subconjuntos de 3 elementos de , contiene una cubierta exacta para , donde y cada elemento en aparece exactamente una vez en $X$ $|X|$ $C$ $X$ $C$ $C'$ $X$ $C' \subseteq C$ $X$ $C'$ ?

PRODUCTO SUBSET

Dada una lista de números y un objetivo , ¿hay un subconjunto de números de $L$ $k$ $L$ cuyo producto sea ? $k$

Para reducir una instancia de X3C a una instancia de SUBSET PRODUCT:

Establecer un mapeo biyectivo entre los miembros de y el primero números primos. Reemplace los miembros de los subconjuntos y con los primos asignados. $X$ $|X|$ $X$ $C$
Para cada subconjunto en , multiplique sus miembros juntos; la lista de productos resultante es para la instancia SUBSET PRODUCT. Debido a que los números primos se usan para el mapeo en el paso 1, se garantiza que los productos serán equivalentes si los subconjuntos son equivalentes por el teorema de factorización único . $C$ $L$
Multiplica los miembros de juntos; el producto resultante es el valor para la instancia de SUBSET PRODUCT. $X$ $k$

Los factores primos de son exactamente los miembros de . Los factores primos de los números en corresponden exactamente a los miembros de los subconjuntos de Por tanto, cualquier solución a la nueva instancia SUBSET producto puede ser transformado en una solución x3c mediante la asignación de los miembros de solución de de nuevo a los subconjuntos en . $k$ $X$ $L$ $C$ $L$ $C$

Cada uno de los 3 pasos de transformación implica operaciones que son polinómicas al tamaño de la entrada o el tamaño de un miembro de . El primero los primos se pueden generar en el tiempo O ( ) utilizando el tamiz de Eratóstenes y se garantiza que encajan en el espacio mediante el teorema del número primo . $|X|$ $X$ $|X|$ $|X|$ $O(|X|^2 \ln |X|)$

Kyle Jones
fuente

+1, pero para que la reducción pase, creo que necesitamos que la primera | X | los números primos se pueden representar en una cantidad de bits que es polinomial en | X | - ¿Tengo razón sobre esto, y si es así, tenemos esa garantía?

j_random_hacker

Excelente punto He agregado un párrafo para abordar eso.

Kyle Jones

¡Gracias, ese teorema lo consolida! No es una trampa, pero de acuerdo con la página a la que se vinculó, el número primo k es aproximadamente k log k, y dado que el Tamiz de Eratóstenes aparentemente calcula todos los primos hasta n en el tiempo O (n log log n) , sustituyendo n = k log k parece dar un tiempo de O (k * log (k) * log (log (k log k))), en lugar de O (k) (su O (| X |)), para calcular la primera k prepara de esa manera.

j_random_hacker

Kyle Jones, ¿no es crítico que el paso 3 cree un número

de tamaño exponencial? ¿Es esta reducción realmente del tiempo polinomial?

k

$k$

user1742364

@ user1742364 No, porque calcular

no requiere un número exponencial de operaciones o requiere almacenar un número exponencial de bits. Computación

requiere

multiplicaciones y multiplicación es, en el peor de los casos, una operación

. Mientras que

será exponencialmente mayor que el primo

más grande en

, el número de bits necesarios para almacenar

será

k

$k$

k

$k$

| X |

$|X|$

O (n^{2})

$O(n^2)$

k

$k$

P

$P$

X

$X$

k

$k$

O (\log P)

$O(\log P)$

Kyle Jones

De acuerdo con [ 1 ]: Sí, es

También cito la misma referencia: Comentarios: Existe una sutil distinción técnica entre esto y el Problema 42: el primer caso tiene un algoritmo pseudoeficiente obtenido al permitir que los números se representen en unario; a menos que todos los problemas NP-completos puedan resolverse mediante algoritmos rápidos, sin embargo, el problema del subconjunto de productos no puede resolverse mediante métodos 'eficientes' que utilicen incluso esta representación de entrada irrazonable.

Eche un vistazo a [2] para ver una reducción. [2]: Compañeros, Michael y Neal Koblitz. "Complejidad de parámetros fijos y criptografía". Álgebra aplicada, algoritmos algebraicos y códigos de corrección de errores (1993): 121-131.

AJed
fuente

Una reducción o cita real en un artículo de revista sería bueno, si es posible.

templatetypedef

@templatetypedef En Garey y Johnson, la reducción es a la cobertura exacta en 3 sets. Debido a la comunicación privada con Yao.

AJed

La reducción en el papel de criptografía es por un problema diferente, en el que el producto objetivo se reemplaza por congruencia con un número objetivo módulo un módulo dado en la instancia. (Aunque si entiendo la prueba correctamente, solo obtienen una dureza débil de todos modos porque el módulo es de magnitud exponencial).

Jeffrey Bosboom