Algoritmi che corrono in tempo polinomiale se p= np

Question

su wikipedia , dice che ci sono alcuni algoritmi che avrebbero corsoin tempo polinomiale se e solo se p= np.Hanno dato un esempio (senza citazione), ma ci sono altri?Ho provato a cercarli e non riuscivo a trovare nessuno.

Answer 1

Wikipedia sta descrivendo l'algoritmo universale di Levin.Questo è un algoritmo per problemi verificabili, che è competitivo con l'algoritmo ottimale (in un certo senso).In particolare, lo stesso identico approccio funzionerebbe per qualsiasi problema in NP, non solo sottoinsieme-somma.