Fehlerkorrekturen zu alten Vorlesungsfolien

• Hier verzeichnete Änderungen sind in der aktuellen (!) Foliensammlung im Netz bereits integriert.
• Nicht verzeichnet sind Tippfehlerkorrekturen und "kosmetische Änderungen" (Layout) sowie Änderungen zwischen Vorabversionen und Vorlesungsversionen.

Danke für Mitteilungen über aufgespürte Fehler.

463, SK-Definition: Die Konstanten 0 und 1 gibt es in der üblichen Definition ebenfalls als zusätzliche Eingaben "umsonst" (lassen sich ansonsten natürlich auch z.B. als $AND(x,\bar{x})$ bzw. $OR(x,\bar{x})$ generieren, was höchstens zwei zusätzliche Bausteine erfordert).

469, Parallel Computation Thesis: $\text{TM-Zeit}\underset{}{\to }\text{TM-Platz},$ $\text{SK-Größe}\underset{}{\to }\text{SK-Tiefe}$ (Mathias Schwarzhoff).

480: $2^{n+1}\underset{}{\to }{2}^n$ (Madeleine Theile).

482: Die Größe der Hilfsinformation ist $O(s(n)\; logs(n)),$ der Platzbeitrag für das Notieren der Kopfposition auf dem Hilfsinfoband ist $log(s(n)\; logs(n)),$ was in der O-Notation aber dasselbe ist wie auf der Folie angegeben (es reicht eine polynomielle Schranke für die Länge der Hilfsinformation in $s(n)).$ Ein Beitrag derselben Größenordnung muss gemäß der Definition des Platzes für nichtuniforme Turingmaschinen noch hinzuaddiert werden, was aber ebenfalls asymtotisch keine Rolle spielt.

485: Die Simulation von TMs durch BPs liefert nur eine Beschränkung der Länge der Rechenwege des BPs durch die Rechenzeit der TM, nicht der Länge aller Wege.

501: $a\text{'}=\text{Median}(A)$ bzw. $b\text{'}=\text{Median}(B)$ sind nicht notwendig in der Kandidatenmenge $I$, das wird aber auch gar nicht benutzt. Es reicht der Test, ob $a\text{'}\le \text{mittleres Element von}I,$ bzw. $b\text{'}\le \text{mittleres Element von}I,$ die Argumentation funktioniert dann genauso wie in der Vorlesung beschrieben.

588: Die in der Hagerup-Rüb-Arbeit hergeleitete Ungleichung für die Abweichung vom Erwartungswert "nach oben" gilt tatsächlich nur für nicht zu große $\lambda$, $\lambda \le 1$ ist z.B. eine ausreichende Beschränkung. Allerdings gibt es ähnliche (nicht ganz so gute bzw. einfach zu merkende) Abschätzungen auch für beliebige $\lambda \ge 0$ (siehe Hagerup, Rüb und Motwani, Raghavan, "Randomized Algorithms"). Beispielsweise gilt für alle $\lambda \ge 0:$
$\text{Pr}\left\{X\ge (1+\lambda )EX\right\}\le {-\left(\frac{1}{2}{\lambda }^2-\frac{1}{6}{\lambda }^3\right)EX}^{}.$

667: "Klausel $c_i$ der Länge $2n$" $\underset{}{\to }$ "Klausel $c_i$ der Länge $n$".

668+669: Ersetze hier überall konsequent $n$ durch die Bitlänge der Eingabe für Alice bei ${\text{LNE}}_{n,n}$, also $n^2$ (Markus Strauch).

725+727: Voraussetzungen des Lemmas 16.6.11 leicht angepasst an vollständige Version des Beweises im Netz.