Transformationen

Ein schweres Problem lässt sich nicht auf ein leichtes Problem reduzieren – es sei denn, dass die Schwierigkeit in der Transformation versteckt ist. Denn das schwere Problem ist nicht schwer, wenn es sich auf dem Umweg über das leichte Problem leicht lösen lässt. Dagegen lässt sich ein leichtes Problem ohne Weiteres auf ein schweres Problem "reduzieren". Wir zeigen dies, indem wir das Sortierproblem auf das Travelling Salesman Problem (TSP) reduzieren (Bild 1). Die hier gewählte Transformation ist dieselbe, die auch beim Beweis der unteren Schranke für die Berechnung der konvexen Hülle vorkommt.

Reduktion

Reduktion von SORT auf TSP

Eingabe:

Folge von Zahlen x₀, ..., x_n-1

Ausgabe:

Die sortierte Folge

Methode:

1. Transformation in einen Fall des Travelling-Salesman-Problems:
1. Bilde Menge von Punkten p_i = (x_i, x_i²) in der Ebene (Bild 2)
2. Berechne x_j = min(x_i)   (in Bild 2 ist j = 4)
2. Löse das Travelling-Salesman-Problem:
1. Berechne die kürzeste Rundreise mit p_j als Startknoten; offensichtlich verläuft die kürzeste Rundreise entlang den Eckpunkten der konvexen Hülle der Punktmenge (rot dargestellt in Bild 2)
3. Rücktransformation:
1. Bilde die Folge der x-Koordinaten der Knoten der Rundreise; dies ist die sortierte Folge (x₄, x₃, x₁, x₀, x₅, x₂ in Bild 2)

4.  

    

   Bild 2:

    

Durch diese Reduktion ist gleichzeitig bewiesen, dass sich das Travelling-Salesman-Problem nicht schneller als in Ω(n · log(n)) Schritten lösen lässt  ;-)   Denn ginge es schneller, dann könnte man schneller als in Ω(n · log(n)) Schritten sortieren – dies ist aber nicht möglich, denn Ω(n · log(n)) ist eine untere Schranke für das Sortierproblem.