Weiterfuehrendes

Turing-Grade

Wir haben gesehen: Es gibt berechenbare und unberechenbare Funktionen, und entscheidbare und unentscheidbare Mengen.
Manche unentscheidbare Mengen sind r.e. (Bsp: Halteproblem), andere sind es nicht (Bsp: Komplement des Halteproblems). Diese beiden Mengen sind aber "gleich kompliziert" im Sinne der Turinggrade bzw der Orakelberechnungen: Gegeben eine Menge A, kann man die charakteristische Funktion von A als Grundfunktion zu einer neuen Art von Maschine dazugeben; dann kann man sich wieder fragen welche Mengen mit dieser neuen Registermaschine entscheidbar sind ("rekursiv in A"). Natuerlich ist das Komplement von H rekursiv in H. Es gibt aber viel kompliziertere Mengen: es sind ja fuer ein gegebenes A immer nur abzaehlbar viele Mengen rekursiv in A. Fuer je abzahlbar viele Mengen gibt es also eine Menge B die nicht rekursiv in irgendeiner dieser Mengen ist.

Beispiele:

Unterschiede innerhalb der berechenbaren Funktionen: Komplexitaetstheorie

In die andere Richtung sind natuerlich auch nicht alle entscheidbaren Mengen gleich schwierig: Manche Probleme kann man leicht (zB: schnell) loesen, andere sind komplizierter. Das fuehrt zur Komplexitaetstheorie. Die uebliche (praktisch wichtigere) Moeglichkeit, Komplexitaet zu definieren, ist dynamisch: Man misst wieviel Zeit (oder: Speicherplatz etc) bei einer Berechnung verwendet wird.

Kolmogorov Komplexitaet

Eine Alternative zur dynamischen Komplexitaet ist die statische Komplexitaet: Die Komplexitaet eines (entscheidbaren) Problems ist die minimale Groesse des Sourcode eines Loesungsalgorithmus. Das entspricht der Kolmogorov-Komplexitaet, die sehr amuesante Eigenschaften hat.
Kolmogorov-Komplexitaet ist auch fuer Strings interessant: Sei s ein endlicher String. Die k.kompl von s ist die Laenge der kuerzeste sourcecode so dass P auf Input 0 den output s liefert.
Bsp: Die ersten 10^10 stellen von pi haben sehr geringe komplexitaet. Ein "Zufalls-Sting" mit 10000 Zeichen hat eine viel hoehere Komplexitaet.
Bem: Die ersten n Stellen von pi, wobei n eine grosse, "zufaellige" zahl ist, haben aber eine groessere Komplexitaet; Dieser Effekt ist nicht immer gewuenscht. Man kann also auch die komplexitaet definieren als der kleinste source code der auf input laenge(s) den output s liefert etc etc

Die Kolmogorov komplexitaet eines strings oder eines Problems ist jedenfalls eine unberechenbare Funktion (und das in recht dramatischer weise). Dadurch ist die Kolmogorov komplexitaet von eher geringer praktischer Bedeutung.

Laufzeit-Komplexitaet

In der dynamischen Komplexitaet beschraenken wir und nur auf die Zeitkomplexitaet. (Der Speicherplatz-fall funktioniert in vielen Aspekten analog.) Einige Bemerkungen:

Beispiele

P ist die klasse der probleme/funktionen, fuer die ein loesungsalgorithmus exisitert, dessen berechnungsdauer polynomiell von der inputgroesse abhaengt. Ein problem ist in der klasse NP, wenn es durch eine nichtdeterministische Computerprogramm (das "gut raten" kann) in polinomieller zeit entschiden werden kann.

ein nichtdeterministisches Computerprogramm ist wie folgt definiert:
erstmal interessieren wir uns ausschliesslich dafuer ob die maschine p haelt oder nicht. wenn p auf input x haelt, interpretieren wir das als "x wird von P akzeptiert". Intuitiv: p zaehlt eine menge a auf, wenn sie genau die Element von A akzeptiert. (A ist dann r.e., aber iA nicht rekursiv)
weiters modifizieren wir den begriff des programms so dass zeielnnummern nicht mehr eindeutig sein muessen: es kann meherer programmzeilen mit nummer l geben, wenn programmzeile l ausgefuehrt werden soll kann p ein beliebige diese zeilen waehlen. Wir sagen P akzeptiert x, wenn es eine wahl von programmzeilen gibt, so dass P auf input x haelt.
A ist nichtdeterministisch entscheidbar in t(s) wenn gilt: Es gibt eine nicht-deterministisches Computerprogramm P so dass x in A gdw P auf input x (mit laenge s) fuer EINE wahl der zeilennummern in Zeit hoechstens t(s) haelt.
(Bem: Wenn t rekursiv ist, dann ist A auch rekursiv und nicht nur r.e.)
A is in NP, wenn A nichtdeterministisch entscheidbar fuer irgendein polynom t(s) ist (equivalent: fuer t(s)=s^a+a fuer irgendein a in N).

SAT ist das Entscheidungsproblem fuer Aussagenlogik, also die Frage ob fuer die Formel phi mit s verschiedenen Aussagenvariablen irgendeine der 2^s vielen Belegungen den wahrheitswert wahr (fuer phi) liefert.
Man kann (recht einfach) sehen dass SAT in NP ist. (Man muss ja nur richtig probieren.) Der offensichtliche deterministische Algorithmus ist aber exponentiell.
Man kann auch sehen (schon tiefsinniger): SAT ist NP vollstaendig: Wenn SAT in P ist, dann ist jedes andere Problem in NP ebenfalls in P, d.h. dann ist P=NP

Ist P=NP? Allgemein word angenommen dass nein, aber beweisen kann das im Moment niemand.