¿Suma de subconjunto, solución de programación dinámica de tiempo pseudo-polinomial?

8

Encontré el problema P vs NP hace algún tiempo y recientemente he trabajado en el problema de la suma de subconjuntos. He leído el artículo de Wikipedia sobre el problema de la suma de subconjuntos, así como la pregunta Algoritmo de suma de subconjuntos

He analizado el problema y encontrado algunas soluciones, pero hasta ahora parecen ser NP, creo que puedo hacer un algoritmo suficientemente rápido en tiempo NP.

Mi problema es que no soy bueno en teoría, por lo que no me ayuda mucho hablar sobre el teorema de Cook-Levin o las máquinas de Turing no deterministas.

Lo que me gustaría es una explicación del subconjunto de programación dinámica de tiempo pseudo-polinomial que se suma en Wikipedia.

Lo he leído y creo que entiendo el concepto general de por qué es NP en lugar de P (relacionado con el tamaño de la entrada en lugar de las operaciones con él), pero no entiendo el algoritmo.

Agradecería que alguien pusiera un ejemplo con algunos números y cómo funciona. Me ayudaría mucho porque:

  • Dame ideas para mejorar mi algoritmo futuro
  • Ayúdame a entender intuitivamente cuando un algoritmo es pseudopolonmial en lugar de NP.
algorithms dynamic-programming Comunidad
fuente
1
crab.rutgers.edu/~guyk/ex/part.pdf
Robert Harvey
1
cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Notes/…
Robert Harvey
2
¿Cuál es la pregunta? Inicialmente pensé que pedías un ejemplo de cómo funciona el algoritmo al que vinculas, pero seguí el enlace y ya hay un ejemplo allí.
rgrig
2
También tengo problemas para entender las publicaciones, no está claro qué se pregunta. por cierto, cada problema en P también está en NP. Supongo que te refieres a NP-complete en lugar de NP en varios lugares de tu publicación. Finalmente, no tiene sentido decir que un algoritmo está en NP, NP es una clase de lenguajes, no algoritmos. Supongo que tiene la idea errónea común de que NP significa algoritmo de tiempo no polinomial (o tiempo exponencial).
Kaveh
2
Si limita el tamaño de los valores en la entrada (limita el número de bits para que cada valor sea logarítmico en el número total de bits de la entrada), entonces el problema puede resolverse en tiempo polinómico usando programación dinámica. Si no están delimitados, pueden tener valores que son exponencialmente grandes y el tamaño de la tabla para la programación dinámica sería exponencial.
Kaveh

Respuestas:

5

Reformulando el comentario de Kaveh como respuesta:

Si limita el tamaño de los valores en la entrada (limita el número de bits para que cada valor sea logarítmico en el número total de bits de la entrada), entonces el problema puede resolverse en tiempo polinómico usando programación dinámica. Si no están acotados, pueden tener valores que son exponencialmente grandes y el tamaño de la tabla para la programación dinámica sería exponencial.

jmite
fuente