Cómo determinar si un algoritmo es NP o no

Answer 1

NP no se aplica a algoritmos, se aplica a problemas.

Un problema es NP si es fácil verificar una solución. Puede que no sea fácil encontrar dicha solución, pero dada una solución candidata, podemos verificar fácilmente si es realmente una solución o no.

Por ejemplo, considere el problema del vendedor ambulante. Tenemos un gráfico que representa ciudades y carreteras. El vendedor necesita encontrar una ruta que atraviese todas las ciudades exactamente una vez, que sea lo más corta posible. Digamos que necesitan encontrar una ruta más corta que algún umbral [math] x [/ math]. Dada una solución candidata, simplemente sumamos todas las distancias y verificamos si esto es o no más corto que [math] x [/ math]. Es bastante fácil, y el tiempo que tome será aproximadamente lineal en el número de ciudades.

Sin embargo, encontrar si tal solución existe o no está lejos de ser trivial; de hecho, se sabe que es NP completo (si encontramos una solución eficiente, que lleva tiempo polinomial en el número de ciudades, podemos encontrar dicha solución a cualquier problema de NP).

Answer 2

Probar que algo está en NP suele ser bastante fácil. Te imaginas que algunos Oracle te dan una solución al problema. Luego verá si hay una manera de verificar que la solución sea correcta utilizando solo algoritmos de tiempo polinomiales.

Por ejemplo, considere el problema de “¿Cuál es el número más pequeño en esta lista?”. Se imagina que Oracle le dice: “El número más pequeño es 4”. Recorre la lista, busca números menores que 4, y no encontrará ninguno. Ahora sabrá que el número más pequeño es de hecho 4. Solo le tomó O (n) pasos, un algoritmo de tiempo polinómico.

Por supuesto, eso fue demasiado fácil, ya que ese problema está en P. No es difícil encontrar un algoritmo de tiempo polinómico incluso sin Oracle. Pero hay otros casos en los que no parece haber un algoritmo de tiempo polinómico para encontrarlo, aunque haya uno para verificarlo. Un ejemplo famoso es 3SAT, donde está buscando asignaciones de variables (a = verdadero, b = verdadero, c = falso, d = verdadero, etc.) y desea ver si algún conjunto de declaraciones (a AND b AND NOT c; NO a Y NO D) son todas verdaderas. Es fácil verificar una solución propuesta, pero parece que no hay mejor manera de encontrar una solución que probar todas las posibilidades, lo que lleva tiempo [matemático] O (2 ^ n) [/ matemático].

Ese problema y muchos otros están en NP pero no (aparentemente) en P. En particular, ese es NP-complete: si puede resolverlo en algún momento, puede resolver TODOS los problemas de NP en ese momento.

Probar un problema es NP-complete es mucho más esfuerzo: generalmente tiene que demostrar que es equivalente a algún otro problema NP-complete conocido.

La verdadera pregunta es si hay problemas NP-completos que no están en P. Esa es otra ‘caldera de peces’.