Todos son igualmente “duros” , en el sentido más fundamental: si pudieras resolver cualquiera de ellos de manera eficiente, podrías resolverlos de manera eficiente. Ese es el sorprendente teorema de Cook y Levin que crea los conceptos de NP-dureza y NP-integridad en primer lugar.
Pero hay al menos una forma interesante en la que un problema de NP completo puede ser “más difícil” que otro. Muchos problemas de NP completo se pueden expresar como problemas de optimización: está tratando de encontrar una disposición que haga que un valor sea lo más grande o lo más pequeño posible. Pero si no podemos encontrar una solución óptima exacta , es de esperar que al menos podamos encontrar una solución casi óptima, ¿verdad? Para algunos problemas, como el problema del embalaje bin (http://en.wikipedia.org/wiki/Bin…), podemos hacerlo. Si desea utilizar solo un 1% más de bins que el mínimo básico (más uno), puede hacerlo en tiempo polinómico. En la práctica, las personas confían en este tipo de aproximación todo el tiempo.
Pero luego están los problemas inabordables : incluso encontrar una solución aproximada es difícil. Los clásicos aquí incluyen el problema de cobertura del conjunto (http://en.wikipedia.org/wiki/Set…) y MAX-3SAT (http://en.wikipedia.org/wiki/MAX…). Para el problema de la cobertura de conjuntos, si desea mantener un 1% más de conjuntos de los necesarios, eso es difícil; si no quieres usar más del 50% más de lo necesario, es difícil; incluso si desea permanecer en solo k veces más conjuntos que la mejor solución, eso es difícil, para cualquier k fijo . Si pudieras lograr cualquiera de estos de manera eficiente, entonces podrías dar la vuelta y resolver eficientemente cualquier problema de NP completo, ¡completamente! Ay.
- Cómo convertir entre índice basado en 1 y basado en 0
- ¿Qué tan difícil es la transición de las matemáticas aplicadas a la informática?
- Regresión logística, función softmax. ¿Por qué utiliza la función exponencial en la función sigmoidea?
- ¿Cómo funcionan la Ley Idempotente y la Ley de Dominación?
- ¿Cómo obtengo un límite superior para T (n) = T (n / 2) + n?
