Algoritmos que correm em tempo polinomial se p= np

Question

na Wikipedia , diz que existem alguns algoritmos que correriamno tempo polinomial se e somente se p= np.Eles deram um exemplo (sem citação), mas há outros?Eu tentei procurá-los e não consegui encontrar nenhuma.

Answer 1

Wikipedia está descrevendo o algoritmo universal de Levin.Este é um algoritmo para problemas verificáveis, que é competitivo com o algoritmo ideal (em algum sentido).Em particular, exatamente a mesma abordagem funcionaria para qualquer problema no NP, não apenas a soma de subconjunto.