Am F3-Skript fällt mir auf, dass nach der NP-Klasse, die ja alle Entscheidungsprobleme umfasst, deren "Laufzeit" mit deterministisch exponenziellem Aufwand lösbar sind, nichts mehr kommt. Ich meine, es sthet nichts von Problemen, die auch mit expo. nicht gelöst werden können (aber trotzdem entscheidbar sind). Die !-Funktion (fac, also 1*2*3 …*n) müsste doch eigentlich noch schneller anwachsen. Oder, wenn auch gewiss sehr konstruiert, eine Funktion die mit Ackermann-Aufwand rechnet, wächst doch wohl auch schneller als NP oder?
Mag einer der Theoretiker mal was dazu sagen, vielleicht mit weiteren Beispielen von solchen schneller als NP-Funktionen und vielleicht auch Problembeispiele dazu?
Wenn ja Danke dafür.

schon mal Google versucht? deine Topicueberschrift klingt doch richtig nach Suchbegriff "Probleme ausserhalb NP"

da steht zum Beispiel dass es auch noch NSpace und PSpace gibt,
die sollten auch im Skript drinstehen, da erinnere ich mich dran,

aber vielleicht fuehrt das auch nur zu einer neuen Frage:
Probleme ausserhalb NSpace ;)

Dumdidum...

In dem Zusammenhang ist vielleicht interessant,
dass es keine "größte" (berechenbare) Zeit- oder
Platzschranke gibt in dem Sinne, dass mit dieser
jedes entscheidbare Problem gelöst werden könnte.
Das ist offensichtlich für Funktionen und
Zeitschranken: für die Zeitschranke T nimmt man
einfach die Funktion [img]http://mokrates.de/cgi-bin/texstring?n%5Cmapsto%201%5E%7BT(n)%2B1%7D[/img],
dafür braucht man sicher mehr als T Zeit (allein,
um die Symbole hinzuschreiben). Für
Entscheidungsprobleme verhält es sich aber genauso.
Man nehme die (entscheidbare!) Menge [img]http://mokrates.de/cgi-bin/texstring?L_T[/img]
aller TM-Kodierungen w mitder Eigenschaft: [img]http://mokrates.de/cgi-bin/texstring?M_w[/img]
rechnet bei Eingabe w mehr als T(|w|) Schritte ohne zu
akzeptieren. (Der geübte Diagonalisierer wird eine
Diagonalisierung erkennen [img]http://www.fb18.de/gfx/28.gif[/img]). Damit ist klar, dass die
Menge nicht in der Zeit T von einer TM M akzeptiert werden
kann, denn:

Wenn M seine eigene Kodierung akzeptiert, braucht M nach
Definition von [img]http://mokrates.de/cgi-bin/texstring?L_T[/img] dazu mehr als T(|<M>|)
Schritte. Wenn M seine Kodierung aber nicht akzeptiert,
ist die Kodierung in [img]http://mokrates.de/cgi-bin/texstring?L_T[/img] und damit
[img]http://mokrates.de/cgi-bin/texstring?L(M)%5Cne%20L_T[/img]. In jedem Fall ein Widerspruch.


Genauso kann man mit dem Platzbedarf argumentieren, da
muss man sich allerdings noch überlegen, dass das analog
konstruierte [img]http://mokrates.de/cgi-bin/texstring?L_S[/img] (für eine Platzschranke
S) auch entscheidbar ist.

Bei NP oder PSpace ist also noch (lange) nicht Schluss.
Und zum Beispiel gibt es Mengen, für die eine akzeptierende
TM mindestens n! Schritte bei Eingabelänge n braucht.