Polynomial Reduction
Eine Polynomialreduktion wandelt Problem A in Polynomialzeit in Problem B um; wenn B lösbar ist, dann auch A, was zum Nachweis der NP-Schwere verwendet wird.
Zweck
Nachweis der Problemschwere und Übertragung der Lösbarkeit; ein zentrales Werkzeug der Komplexitätstheorie.
Mechanismus
A ≤_p B: Es gibt eine Polynomialzeit-Funktion f, die Instanzen von A auf Instanzen von B abbildet, sodass A(x)=B(f(x)). Wenn B∈P, dann A∈P. Ist A als NP-schwer bekannt und gilt A≤_p B, dann ist B NP-schwer.
Anwendungsfälle
- Komplexitätsbeweise
- NP-schwere Reduktionen
- Problemklassifikation