Woraus besteht Time(t)?
Alle Sprachen, die von
Mehrband Turingmaschinen entschieden wird
bei der die Funktion O(t(n)) die Laufzeit der Maschine mit Eingabelänge |w| = n beschränkt
Woraus besteht Space(s)?
Alle Sprachen, die von einer
Mehrband Turingmaschine entschieden wird
wobei O(s(n)) Speicherbedarf mit EIngabe |w| = n beschränkt
! Reines Eingabeband zählt nicht zum Speicherbedarf (nur Arbeitsband)
Was bewirkt die O-Notation
Einordnung der Sprachen zu TIME(t) bzw. SPACE(s)
Komplexitätsklasse P
TIME(n^k) oder
TIME(n^O(1)) -> oben nur Konstanten
Unterschied einer NTM zur TM in der Definition
Gleich, bis auf die Übergangsfunktion -> dies ist dann eine Potenzmenge mit möglichen nächsten Schritten und den jeweiligen Zuständen
Woraus besteht NTIME(t)
NTM entschieden wird
wobei O(t(n)) Laufzeit der Maschine auf allen Berechnungspfaden mit Eingabe |w|=n beschränkt
Woraus besteht NSPACE(s)
Wie NTIME für Speicherbedarf
Woraus besteht Komplexitätsklasse NP
NTIME(n^k) oder
NTIME(n^O(1))
Satz 1 (TM Mehrband->Einband)
Jede Mehrband TM, die in Zeit t arbeitet kann von einer Einband TM in Zeit O(t^2) simuliert werden
Satz 2
Jede Merhband TM, die in Zeit n arbeitet kann von einer 2-Band TM simuliert werden, die in Zeit O(t*log(t))
Satz 3 (NTIME TIME)
Sei t(n) >= n, dann gilt NTIME(t(n)) c= TIME(2^O(t(n)))
Zuletzt geändertvor einem Jahr