Fachrat Informatik - Forum

Quoted

Original von Dr. Jekyll
Weiss jemand, warum LOGITADD in konstanter Tiefe realisierbar ist? Die notwendingen k Iterationen jede für sich haben konstante Tiefe, aber je nach Länge der Eingabe sind ja mehr und mehr dieser Iterationen notwendig, die jeweils auf das Ergebnis der vorherigen angewiesen sind, also auch nicht parallel erfolgen können. Somit kann ich mir nicht vorstellen, warum der resultierende Schaltkreis konstante (also unabhängig von der Eingabelänge) Tiefe hat.

Das kommt daher, daß man die Iterationsschritte selber nicht berechnet, sondern nur die Funktion, die diese Schritte darstellen.

Jedes Ausgabebit hängt von l(2)(n) * l(3)(n) * ... * l(k)(n) Bits aus der ersten Iteration ab (also s_k). Da gilt l(2)(n) * l(3)(n) * ... * l(k)(n) = O(log n) -- läßt sich nachrechnen, kann ich hier mal machen, wenn es jemand wissen möchte -- hängt also jedes Ergebnisbit nur von O(log n) Bits der s_k ab. Jedes Ergebnisbit läßt sich also durch eine Funktion g_i: {0, 1}^{O(log n)} -> {0, 1} berechnen.

s_k ist in konstanter Tiefe und polynomieller Größe berechenbar.

Da jede Boolesche Funktion f: {0, 1}^m -> {0, 1} über der Basis B_1 in konstanter Tiefe und Größe O(2^m) berechnet werden kann (siehe Übung), lassen sich die g_i in konstanter Tiefe und Größe O(2^{O(log n)}) = O(n) berechnen.

Insgesamt besitzt der Schaltkreis für LOGITADD demnach konstante Tiefe und polynomielle Größe.

Quoted

Original von Dr. Jekyll
PS.: Herzlichen Glückwunsch nachträglich

Danke.