¿Detección de relación entera para Subset Sum o NPP?

¿Hay alguna forma de codificar una instancia de Subset Sum o el problema de partición numérica para que una solución (pequeña) a una relación entera produzca una respuesta? Si no es definitivamente, ¿en algún sentido probabilístico?

Sé que LLL (y quizás PSLQ) se han utilizado con éxito moderado en la resolución de problemas de Subconjuntos en la región de 'baja densidad', donde el rango de números elegidos es mayor que , pero estos métodos no se adaptan bien casos de mayor tamaño y fracasan en la región de alta densidad ', cuando el rango de números elegidos es mucho menor que . Aquí baja densidad y alta densidad se refieren al número de soluciones. La región de baja densidad se refiere a las pocas o nulas soluciones que existen, mientras que la alta densidad se refiere a una región con muchas soluciones. $2^N$ $2^N$

En la región de alta densidad, LLL encuentra relaciones enteras (pequeñas) entre las instancias dadas, pero a medida que aumenta el tamaño de la instancia, la probabilidad de que la relación sea una solución viable de Subconjunto de Suma de Subconjunto o Número de Partición se vuelve cada vez más pequeña.

La detección de la relación de enteros es polinómica dentro de un límite exponencial de óptimo, mientras que Subset Sum y NPP son obviamente NP-Complete, por lo que en general esto probablemente no sea posible, pero si la instancia se dibuja de manera uniforme al azar, ¿podría hacerlo más simple?

¿O no debería siquiera hacer esta pregunta y preguntar si hay una manera de reducir el límite exponencial de la respuesta óptima en lugar de un aumento exponencial en el cálculo?

cc.complexity-theory np-hardness approximation-algorithms reductions subset-sum usuario834
fuente

No recibía ninguna respuesta, así que lo he publicado en mathoverflow: mathoverflow.net/questions/38063/…

user834

Esta es una pregunta muy interesante, también estoy esperando respuestas. Básicamente, está solicitando una reducción de tiempo polinomial (quizás aleatoria) de la suma de subconjuntos o NPP a la relación de enteros. Qué tal esto, si

es el objetivo de su problema de suma de subconjuntos, y

es un conjunto de enteros positivos, con

una solución satisfactoria

t = 0

$t=0$

S

$S$

S^{'}

$S'$

0 = \sum_{a \in S^{'}} a

$0=\sum_{a\in S'} a$

a_{i} \in S

$a_i \in S$

\sum_{i} a_{i} < 2^{n} - 1

$\sum_i a_i < 2^n-1$

@Marcos Villagra: su comentario es un poco difícil de analizar ... se puede integrar el problema como un problema de partición de suma / número de subconjunto en una red (vea aquí para una revisión), la pregunta es encontrar una manera de restringir los coeficientes a conjunto deseado (0,1 o -1,1, por ejemplo). LLL encontrará una relación entera, incluso pequeña, pero solo un 2 o 3 como coeficiente la invalidará como una respuesta de partición de suma / número de subconjunto.

user834

Sea m el logaritmo del mayor número. Si entonces es solucionable en tiempo polinómico usando programación dinámica. En general, cada algoritmo conocido toma al menos $m=O(\log n)$ $\Omega(2^{m})$ $m=\omega(\log n)$ $m=o(n)$

Sin embargo, Flaxman y Przydatek proporcionan un algoritmo que resuelve los problemas de suma de subconjuntos de densidad media en el tiempo polinómico esperado.

Verifique esta referencia:

Flaxman y Przydatek, resolviendo problemas de suma de subconjuntos de densidad media en el tiempo polinómico esperado

Mohammad Al-Turkistany
fuente

Este resultado es solo para elegir los números en la instancia de Subset Sum significativamente más bajos de lo que quiero. Eligen el rango de números en el orden de log (n) ^ 2, mientras que estoy interesado en el rango de números en el orden de 2 ^ n. Hay algoritmos bien conocidos para resolver Subset Sum cuando el rango de números está restringido a ser tan bajo y parece que solo han ampliado un poco este rango, lo cual es genial, simplemente no es lo que estaba buscando. Gracias de cualquier forma.

user834

¿Detección de relación entera para Subset Sum o NPP?

Respuestas: