Wir wollen zuletzt noch auf die Ähnlichkeiten zwischen Entscheidungs- und Optimierungsproblemen eingehen. Bei Turingmaschinen interessieren wir uns für die Akzeptanz bzw. das Entscheiden von Sprachen. Bei einer vorgelegten Eingabe, soll die Turingmaschine im Rahmen der Zeitschranke anhalten und positiv oder negativ antworten (in diesem Abschnitt haben wir die Zeitschranken zunächst nur für Erfolgsrechnungen eingeführt, wir werden aber im nächsten Abschnitt sehen, dass wir dies auch für unsere Zwecke auf alle Rechnungen erweitern können). Z.B. erhält man als Eingabe einen Graphen \(G\), zwei Knoten \(s\) und \(t\) und eine Schranke \(k\) und die Frage ist, ob ein Pfad von \(s\) nach \(t\) existiert, der höchstens den Wert \(k\) hat. In der Praxis interessiert man sich aber meist mehr dafür, den Wert für \(k\) zu optimieren oder den Pfad, von \(s\) zu \(t\) zu bestimmen. Entscheidungs- und Optimierungsprobleme lassen sich aber meist gut ineinander umwandeln, so dass eine Lösung des einen auch zu einer Lösung des anderen führt. Dass man mit einer Lösung des Optimierungsproblems auch das Entscheidungsproblem lösen kann, liegt meist auf der Hand, da man dann ja den besten Wert kennt. Andersherum funktioniert es meist, indem man z.B. den Wert \(k\) aus dem obigen Beispiel wie bei einer binären Suche immer weiter halbiert oder indem die Probleminstanz sukzessive geändert wird, hier z.B. indem einzelne Knoten entfernt werden und geprüft wird, ob ein Entscheidungsverfahren immer noch akzeptiert. Wir merken uns an dieser Stelle einfach, dass die Entscheidungs- und die Optimierungsvariante eines Problems so ähnlich sind, dass man, wenn man das eine schnell (also mit einem Polynomialzeitalgorithmus) lösen kann, auch das andere schnell (mit einem Polynomialzeitalgorithmus) lösen kann. Es genügt daher, sich auf die, für die Theorie angenehmeren, Entscheidungsvarianten zu konzentrieren und mit diesen eine für die Praxis relevante Theorie aufzubauen.