- Registriert
- 23.1.2020
- Beiträge
- 1.039
- Reaktionen
- 5.542
- Punkte
- 406
- Checks
- 10
Zeigen Sie, dass eine Sprache L genau dann in NTIME(t) ∩ co-NTIME(t) liegt, falls eine t- zeitbeschränkte NTMM mit L(M) = L existiert, die auf allen Eingaben strong ist. (Blum Komplexität) Eine partielle Funktion Φ, die (geeignete Kodierungen von) TMs M und Eingaben x in die natürlichen Zahlen abbildet, heißt Komplexitätsmaß, falls sie folgende Axiome erfüllt.
