Si un problema np-hard se resuelve en tiempo polinómico, ¿es eso una prueba de que p = np o este problema se ha clasificado incorrectamente?

Sí. Cada problema en NP-hard es al menos tan difícil como NP-complete. NP-complete es un subconjunto de NP-hard. Hay otras clases que son subconjuntos de NP-hard (por ejemplo, PSPACE.) Que son aún más difíciles de resolver, y son aún menos propensos que los problemas de NP a ser resueltos en tiempo polinómico de manera determinista. (Se ha demostrado que P es un subconjunto adecuado de EXPTIME, que es parte de NP-hard, por lo que ciertamente no incluirá eso).

Para ponerlo en un diagrama, extraído de Wikipedia:

Hay un problema semántico aquí. Se ha comprobado que muchos problemas de NP-Complete son de NP-Complete según las estrategias de búsqueda requeridas. Pero cuando se les da la respuesta correcta, se pueden validar más rápido que NP-Complete (creo que el vendedor viajero es un ejemplo de esto).

Para que usted pueda decir algo significativo sobre la hipótesis p = NP, tendría que no solo resolver un problema, sino crear una estrategia de solución garantizada para resolver una clase completa de problemas en tiempo polinómico.
Pero si hicieras eso, probarías una amplia clase de problemas que se sabe que son equivalentes en algún sentido. Sin embargo, debo mencionar que hay un gran subconjunto de problemas polinómicos, que solo puede terminar en un tiempo razonable cuando se baja a la computación cuántica (o peor) y si hubo un mapeo de problemas no polinómicos en tiempo polinómico, entonces muchos de la clase np-complete se garantizaría que se mapearía en la “parte difícil” del tiempo polinomial, por lo que es muy posible que hagamos este descubrimiento y la respuesta todavía salga como “no con las computadoras de hoy en día para la gran n”.

Pero, en teoría, si se te ocurre un algoritmo eficaz y repetible para resolver uno de los problemas completos de np en tiempo polinómico, entonces deberíamos poder decir: “Al menos esto se puede resolver más rápido que en tiempos exponenciales” para toda la clase .

Significa que se ha clasificado incorrectamente.

Depende de cada caso específico de cada problema específico, pero generalmente hay muchos casos en los que P no es igual a NP.

Entiendo que la cuestión de P vs. NP es en realidad una cuestión de ergodicidad computacional en el espacio de solución .

En algún lugar del espacio de fases de las posibles configuraciones del sistema, hay estados que son “soluciones correctas” a ciertos problemas que pueden verificarse mediante una “ruta computacional corta”: esto es análogo a resolver un laberinto al revés, que generalmente es mucho más fácil que resolverlo hacia adelante (depende de los detalles del diseño del laberinto, pero se entiende la idea).

Resolver un laberinto hacia adelante es mucho más difícil porque la topología del laberinto significa que el espacio combinatorio de posibles soluciones puede crecer muy rápidamente, y usted no sabe si una rama del camino es la solución o no hasta que llegue a su final, y entonces el P vs La pregunta de NP en realidad contiene “el problema de la detención”, que se ha demostrado que es indecidible (Turing, 1936).

Por lo tanto, si el problema de detención no se puede resolver universalmente, esto implica que hay caminos de solución de laberinto que no se pueden predecir sin un cálculo exhaustivo, y cuyo tiempo de cálculo de la solución tampoco se puede predecir. Entonces P no es igual a NP.

Si cree que ha mostrado que un problema NP-completo tiene un algoritmo de tiempo polinómico, las posibilidades más probables son:

1. Tu algoritmo no es correcto.
2. Tu algoritmo no es polinomial.
3. El problema que resuelve el algoritmo no es en realidad NP completo.

No, eso no es una prueba de p = np. Cada problema p también es un problema np, por lo que ya hay toneladas de problemas np-hard que se pueden resolver en tiempo polinómico. La conjetura indica que TODOS los problemas np-hard se pueden resolver en tiempo polinómico, lo que es una afirmación muy diferente.