Frage zum Lehrbuch

Question

 Auf Seite 333 , die Formel in letzte Zeile:tX(w) = pf (∣w∣) + tY (∣f (w)∣) + pg(∣fY(f (w))∣) habe ich Frage auf dem dritte Term.
da die Funktion tT(w) auf Seit 6 als Zeitbadarf def. Soll tY auch als Funktion von ein Eingabe Wort def.oder?Wie versteht man die  Betrag in tY steht? also tY von ein Zahl nicht einen Eingabewort. Kann das ein Schreibfehler sein? also tY(f(w)).  

PS:die folgende Beweiseschritt haben wir die  Abschätzung auch auf dieser Basis. und bis zum letzt Schritt auf die letzte Formel auf Seite 335 haben wir nun tY als Polynom angenommen. Wenn es echt ein Fehler ist ,werde die Zwischenschritten auch ein Problem. 

Es wäre hilfreich wenn jemand einmal checken könnte.
Vielen Dank

 

 

Comments

Ich werde es überprüfen, bin heute allerdings mit der Bonusklausur beschäftigt. Auf den ersten Blick denke ich, dass es $t_X(|w|)$ vor dem Gleichzeichen heißen müsste und die Funktionen $t_X, t_Y$ nicht auf Wörtern sondern auf Wortlängen, also Zahlen arbeiten. Es ist also irgendwo ein Fehler, aber ich denke ein kleiner.

Answer 1

Sie haben da leider (für uns - aber gut für Sie, dass Sie so ein scharfes Auge haben!) einen kleinen Fehler entdeckt. In der Formel soll es nur um Wortlängen gehen, daher müsste es $t_X(|w|)$ heißen. Aber ich gebe zu, dass zusätzlich die Bezeichnungen irreführend sind, denn $t$ hatten wir zuvor für den Zeitbedarf einer Turingmaschine genutzt, und dieser war auf Wörtern, nicht Wortlängen definiert. Besser wäre also ein anderer Variablenname gewesen.

Sie müssen sich mit dieser Berechnung aber gar nicht unnötig lange aufhalten - es geht nur darum zu zeigen, dass die Lösung eines Problems über den Umweg einer Polynomialzeitreduktion nicht mehr als um einen polynomiellen Faktor länger dauern kann als die Lösung des Problems, auf das reduziert wurde. Das ist ja nun nicht so schwierig einzusehen - vielleicht versuchen Sie das einfach mal selbst herzuleiten...

Diese Stelle im Lehrbuch finde ich gerade nicht mehr so ganz gelungen - bei einer Neuauflage werden wir das schöner machen :-)

Danke, dass Sie uns auf die Ungenauigkeit aufmerksam gemacht haben!

Comments

Vielen Dank für Ihre Antwort.  Naja, ich bin nicht sicher ob ich  "bis zum polynomiale Faktoren" richtig verstehe, und versuch die genaue Beweisen zu schauen. Dann bin gesperrt bei die t Funktion . Jetzt ist es ganz klar!

---

Damit meine ich nur, dass wir bei der Lösung über die Reduktion in der Klasse $P$ bleiben, wenn das Problem, auf das reduziert wurde, ebenfalls in $P$ liegt. Wir bleiben also polynomiell und werden nicht plötzlich exponentiell oder so.