Die Komplexitätsklasse P < Wettbewerbe < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 05:20 Fr 27.01.2006 | | Autor: | mathiash |
| Aufgabe | Es sei [mm] P=\bigcup_{c\in\IN}DTIME(n^c) [/mm] die Menge aller Entscheidungsprobleme
(als Mengen von Strings) [mm] L\subseteq\{0,1\}^{\star}, [/mm] für die es eine polynomiell zeitbeschränkte deterministische Turing-Maschine M gibt mit L(M)=L (d.h. M löst das Entscheidungsproblem L).
Zeige: es gibt eine Funktion [mm] t\colon\IN\to \IN [/mm] mit folgender Eigenschaft:
P=DTIME(t(n)) |
Hallo zusammen,
man kann demnach P als deterministische Zeitklasse NUR EINER EINZIGEN Funktion t(n)
charakterisieren, und das liest sich doch hinreichend seltsam, um es für Interessierte ins Forum zu stellen, oder ?
Viele Grüße,
Euer Mathias
|
|
|
