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:

• Gegeben A, dann ist das Haltebroblem H_A der neuen Registermaschine (mit A als Grundfunktion) nicht rekursiv in A (Beweis ganz analog zum Beweis fuer H)
• Folgende Menge B is komplizierter als H: e ist in B, wenn e Goedelnummer einer Registermaschine ist, die eine partielle Funktion mit endlichem Definitionsbereich berechnet.
• Es zeigt sich dass es in diesem Sinn eine sehr komplizierte Hierarchie der Grade der (un)entscheidbarkeit gibt (Turinggrade).

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:

• Eine Funktion (bzw ein Problem) kann verschiedene Loesungs(bzw Berechnungs)programme haben. Wir koennen zuerst mal die Komplexitaet eines bestimmten Algorithmus (nicht der Funktion) untersuchen. Manche Funktionen haben einen optimalen Loesungsalgorithmus (im Sinne des naechsten Punktes), dann kann man die Komplexitaet dieses Algorithmus mit der Komplexitaet der Funktion gleichsetzen. Im Allgemeinen gibt es aber fuer jedes Komplexitaetsmass Probleme ohne optimale Loesung!
• Wir interessieren uns nur fuer die *Wachstumsrate* der Laufzeit in Abhaengigkeit der Inputgroesse, wobei endlich viele Faelle und konstante Faktoren ignoriert werden. Notationell: f ist in O(g) wenn ... (Gruende: alles andere ist stark abhaengig vom computermodell; und auch mathematisch nciht sehr befriedigend zu behandeln)
• Die Komplexitaet einer funktion wie 2^2^x ist notwendigerweise (und trivialerweise) sehr gross, ohne dass notwendigerweise eine grosse "interene" Komplexitaet vorliegen muss. In mancher Hinsicht ist es fuer die Komplexitaetstheorie befriedigender, nur Probleme (d.h. funktionen von N nach {0,1}) zu untersuchen.
• Wir nehemn an, dass der input als binaerstring x der laenge l gegeben ist, und geben die komplexitaet in abhaengigkeit von l an (D.h. s isgt ca ln_2(n)).
• Wir untersuchen also nur Algorithmen bzw Probleme mit beliebig grossem Input. In der Praxis sind natuerlich auch Algorithmen sehr wichtig die auf Input fixer Grosse operieren, zB multiplikation fuer long ints oder floats etc.

Beispiele

• Addition: O(n), d.h. linear
• multiplikation: summer algorithmus ist o(n^2), es gibt aber bessere (zb o(n^a) fuer jedes a groesser 1)
• primzahltest: o(n), d.h. linear (nichttrivial)
• subset-equal-zero problem: np
• travelling salesman problem: np
• sat, aussagenlogische erfuellbarkeit: np
• wahrheit in presburger arithmetik: hyperexponentiell

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.