Satz Laufzeit Determinisierung von Nichtdeterminismus

Einfache Sprache

Der Satz besagt das der Nichtdeterminismus zum Preis der exponentiellen Erhöhung der Laufzeit.

Def. Satz Laufzeit Determinisierung von Nichtdeterminismus

Sei $t(n)$ eine Funktion mit $t(n)\geq n$. Dann hat jede $t(n)$ Laufzeit NDTM eine äquivalente $2^{O(t(n))}$ Laufzeit TM.

Idee: Bei der Simulation wird eine Breitensuche verwendet um eine Akzeptierende Berechnung zu finden. Das heißt wir brauchen $t(n)$ Speicherplatz und die Anzahl der Berechnungen die wir durchsuchen müssen wächst exponentiell mit der Größe der Eingabe.

Beweis: Sei $N$ eine $t(n)$ Laufzeit NDTM. Sei $3D$ die 3-Band TM die nach dem Satz Redundanz von Nichtdeterminismus existiert. $\left[\mathrm{Z\kern-.5em\raise-0.6ex\hbox{Z}}\; D \in 2^{O(t(n))}\right]$ Für eine gegebene Eingabe der Länge $n$ hat der Baum aufgespannt durch die Berechnungen von $N$ höchstens die Tiefe $t(n)$. Jeder Knoten kann höchsten $b$ Kindknoten, wobei $b$ die maximale Anzahl an legalen Auswahlmöglichkeiten von $N$ ist. Also ist die maximale Anzahl an Blattknoten $b^{t(n)}$. $3D$ simuliert nun $N$ indem es diesen Baum mit Breitensuche durchsucht. Es werden also alle Knoten auf Ebene $d$ besucht, bevor die Knoten der Ebene $d+1$ besucht werden. Die Anzahl an Knoten des Baums ist kleiner gleich 2 mal die maximale Anzahl der Blätter. Also durch $O(b^{t(n)})$ nach oben beschränkt. Es dauert $O(t(n))$ von der Wurzel zu beliebigen Knoten zu kommen. Daher hat $3D$ eine Laufzeit von $O(t(n)b^{t(n)}) = 2^{O(tn))}$. Nach dem Satz Redundanz von Nichtdeterminismus ist $D$ eine 3-Band TM. Nach dem Satz Laufzeit zusätzlicher Bänder gibt es eine DTM $D$ die $3D$ mit höchstem quadratischen Mehraufwand simuliert. Also gilt $(2^{O(t(n))})^2 = 2^{O(2t(n))} = 2^{O(t(n))}$.