Algorithmen, die in der Polynomzeit laufen, wenn p= np

Question

auf Wikipedia , sagt es, dass es einige Algorithmen gibt, die laufen würdenBei der Polynomzeit, wenn und nur wenn p= np.Sie gaben ein Beispiel (ohne Zitat), aber gibt es andere?Ich habe versucht, sie aufzusehen und nicht zu finden.

Answer 1

Wikipedia beschreibt den universellen Algorithmus von Levin.Dies ist ein Algorithmus für überprüfbare Probleme, das mit dem optimalen Algorithmus (in gewissem Sinne) wettbewerbsfähig ist.Der genaue Ansatz würde insbesondere für jedes -Problem in NP arbeiten, nicht nur die Subset-Summe.