Algoritmos que se ejecutan en tiempo polinomial si p= np

Question

en wikipedia , dice que hay algunos algoritmos que se ejecutanen el tiempo polinomial, si y solo si p= np.Dieron un ejemplo (sin cita), pero ¿hay otros?Intenté mirarlos y no pude encontrar ninguno.

Answer 1

Wikipedia está describiendo el algoritmo universal de Levin.Este es un algoritmo para problemas verificables, que es competitivo con el algoritmo óptimo (en cierto sentido).En particular, el mismo enfoque exacto funcionaría para cualquier problema en NP, no solo subsecable-suma.