Informatik

Wie zeigt man NP-Schwere durch Reduktion?

Man nimmt ein bekannt NP-schweres Problem $A$ und konstruiert in polynomieller Zeit eine Abbildung auf das neue Problem $B$.

Wichtig ist die Richtung: $A\le_p B$. Dann wäre ein effizienter Algorithmus für $B$ auch einer für $A$.