¿Problema de suma del subconjunto es NP-completo?

Question

Si sé correctamente, subconjunto suma problema es NP-completo. Aquí tiene una matriz de n enteros y se le da una suma de destino t, se tiene que volver a los números de la matriz, que se puede resumir a la de destino (si es posible).

Pero no puede este problema se resolvió en el tiempo polinomio por el método de programación dinámica donde construimos una tabla de n X t y tomar casos como el de decir que el último número es sin duda incluidos en la salida y, a continuación, el objetivo se convierte en t - a[n]. En otro caso, el último número no incluye a continuación, el objetivo sigue siendo la misma t pero matriz se convierte de tamaño n-1. Por lo tanto, esta forma de mantener la reducción del tamaño del problema.

Si este enfoque es correcto, no es la complejidad de este n * t, que es el polinomio? y si esto pertenece a P y también NP-completo (por lo que he oído), entonces P=NP.

Sin duda, me estoy perdiendo algo aquí. Donde está la laguna en este razonamiento?

Gracias,

Answer 1

Si usted expresa las entradas en unario es diferente tiempo de ejecución que si se expresa en una base más alta (binario, más comúnmente).

Así que la pregunta es, para el subconjunto suma, lo que la base es la adecuada? En ciencias de la computación, normalmente por defecto a la siguiente:

• Si la entrada es una lista o colección, nos expresa su tamaño como el número de elementos
• Si la entrada es un número entero, se expresará su tamaño como el número de bits (dígitos binarios)

La intuición aquí es que nos quieren tomar el "pacto" de la representación.

Así que para el subconjunto suma, tenemos una lista de tamaño de $n$ y un destino entero de valor de $t$. Por lo tanto, es común para expresar el tamaño de entrada como $n$ $t=2^k$ donde $k$ es el número de bits necesarios para expresar $t$. Así que el tiempo de ejecución es $O(n 2^k)$ que es exponencial en $k$.

Pero también se podría decir que $t$ es dado en unario. Ahora, el tamaño de $t$$t$, y el tiempo de ejecución es $O(n t)$, que es el polinomio en $n$$t$.

En las reducciones que implican subconjunto suma (y otros problemas relacionados, como la partición 3 partición, etc) nos debe utilizar una única representación si queremos usarlo como NP-Duro problema de reducir de.

Answer 2

Este es uno de los puntos finos a veces olvidadas al aprendizaje sobre el tema. La eficiencia de un algoritmo siempre se mide en lo que respecta al tamaño de la representación de la entrada - ¿cuánto bits que necesita para codificar. En el caso de los números de esta distinción es crucial, ya que el número de $n$ es generalmente representado por $\lg n$ (log en base 2) de bits. Por lo tanto, una solución que es $O(n)$ es exponencial en el tamaño de entrada, por lo tanto extremadamente ineficiente.

El ejemplo clásico de esta distinción es la comprobación de primalidad; incluso el más ingenuo algoritmo es $O(n)$, pero no podemos pensar en algo como esto verdaderamente eficaz, incluso si adoptamos la vida real-enfoque - podemos (o no) trabajar con números con hundereds de los dígitos en una base diaria, y usuales de la aritmética con esos números es bastante rápido (se polinomio en el número de dígitos), pero ingenuo primalidad métodos de prueba nunca va a terminar en la vida real, incluso para los números con cientos de dígitos o menos.

El mismo peligro acecha en cualquier problema que implica números, en el subconjunto particular de la suma.