Links und Funktionen
Sprachumschaltung

Navigationspfad
Sie sind hier: Startseite / Lehre / WS 2015/16 / Komplexitätstheorie / Komplexitaet und Programmiersprachen


Inhaltsbereich

Komplexitaet und Programmiersprachen

Notiz von WS08/09

Plain Text icon proglang.txt — Plain Text, 14 KB (14624 bytes)

Dateiinhalt

SATZ VON COOK: 

Definition (E/A-TM mit Stack): Eine Turing - Maschine mit Stack hat
mindestens 3 Baender: E, A und S. E ist das Nur-Lese Eingabeband, A
das Nur-Schreibe Ausgabeband und S ist ein Stack auf dem zwar gelesen
und geschrieben werden kann, aber immer nur in Stack-Disziplin,
d.h. der Kopf steht immer ganz rechts. Formal besteht hat solch eine
Maschine besondere Quintupel der Form 

(q,s,s',m,q',sa) 

hat, wobei q:Q, s:Sigma^k, s':Sigma^{k-1}, m:{L,R,S}^{k-1},
und sa eine Stack-Aktion ist: 

Entweder

1) sa = IDLE: das Stack-Band und der Stack-Kopf veraendern sich
   nicht. 
2) sa = POP: der Stack-Kopf rueckt eine Position nach links. Ist der
   Kopf schon auf der linkesten Bandposition, so bleibt die Maschine
   stehen. 
3) sa = PUSH(y), y:Sigma. Der Stack-Kopf rueckt eine Position nach
   rechts und schreibt y auf die neue Position. 

Zu Beginn befindet sich auf dem Stack-Band ein bestimmtes Symbol
A. Wird dieses also geloescht, so bleibt die Maschine stehen.  

Eine (nichtdeterministische) TM mit Stack ist f(n)-platzbeschraenkt, wenn nach Ende der
Berechnung auf Input x (auf E geschrieben) die Summe der Laengen aller
Arbeitsbaender ausser S <= f(|x|) ist. Der Stack S kann beliebig lang
sein. 

Die Komplexitaetsklasse (N)SPACE(f(n))+STACK bezeichnet alle Probleme, die
sich mit solch einer (nichtdeterministischen) TM loesen lassen.

Beispiel: Der Beweis des Satzes von Savitch zeigt, dass REACH: : LOGSPACE+STACKw

Satz (Cook): Sei f(n)>=log(n). Es ist SPACE(f(n))+STACK =
NSPACE(f(n))+STACK = TIME(2^c.f(n))

Beweis: Sei M eine SPACE(f(n))+STACK Maschine. Eine globale
Konfiguration von M ist definitionsgemaess eine globale Konfiguration
ohne Beruecksichtung des Stacks S, besteht also aus den Inhalten und
Kopfpositionen aller Arbeitsbaender, sowie der Kopfposition des
Eingabebandes. Man beachte, dass (wegen f(n)>=log(n)) eine solche
globale Konfiguration Platz O(f(n)) verbraucht, deren Zahl also
2^O(f(n)) ist. Sei nun x eine Eingabe, g eine globale
Konfiguration, U ein Symbol. Wir bezeichnen mit 

k(g,U) 

diejenige globale Konfiguration, die erreicht wird, wenn U ge-poppt
wird. Da dies moeglicherweise nie der Fall sein wird, ist k eine
partielle Funktion. Beachte: k haengt implizit auch von der Eingabe
ab. 

Man beachte, dass x in L(M) genau dann, wenn 

k(init,A) eine akzeptierende Konfiguration ist. 

OBdA (Aufraeumen etc) koennen wir von einer einzigen akzeptierenden
Konfiguration Accept ausgehen: 

x : L(M) <==> k(init,A) = Accept.

Nun erfuellt k folgende Rekurrenz: 

k(g,U) = t(g,U), falls das Symbol U im naechsten Schritt gepoppt
wird. t sei dann die entsprechende Folgekonfiguration, die sich aus
dem entsprechenden Quintupel ergibt. 

k(g,U) = k(t(g,U),U), falls das Symbol U stehenbleibt. 

k(g,U) = k(k(t(g,U),V),U), falls das Symbol V gepusht wird. 

Es liegt also eine geschachtelte Rekursion vor, bei deren Abarbeiten
sei es durch Termersetzung, sei es mit Frames wie in Java,  sich
natuerlich wiederum der Stack S reproduziert. 

Der Punkt ist nun, dass wir diese rekursive Funktion anstatt durch
echte Rekursion auch durch dynamische Programmierung, d.h. also durch 
Tabulierung aller 2^O(f(n)) Werte in Zeit 2^O(f(n)) berechnen
koennen. 


War die Maschine urspruenglich nichtdeterministisch, so brauchen wir
eine Relation 

k(g,U,g') <==> ausgehend von g mit oberstem Stacksymbol U kann nach
mehreren Schritten U gepoppt werden und damit Konfiguration g'
eingenommen werden. 

Es gilt

in g kann U sofort gepoppt werden und g' erreicht werden ==> k(g,U,g')
in g kann U stehenbleiben und g' erreicht werden, ausserdem gilt
k(g',U,g'') ==> k(g,U,g'')
in g kann V gepusht werden und g' eingenommen werden. 
Auf der anderen Seite geben wir uns eine 2^O(f(n))-zeitbeschraenkte
Maschine vor. Wir definieren die Funktion

k(x,t,a) = "das Symbol, das an der Stelle a zur Zeit t auf den
Baendern steht". Es gilt: 

k(x,0,a) = init
k(x,t+1,a) = ... k(x,t,.) ... k(x,t,.) ... 

Diese rekursive Funktion kann nun aber mithilfe eines Stacks (dessen
Hoehe exponentiell sein wird) ausgerechnet werden. 




SATZ VON COBHAM

Ziel ist eine Charakterisierung der PTIME Funktionen mittels einer
Einschraenkung der primitiven Rekursion. 

Notationsrekursion: 

f = rec(g,h) bedeutet: 

f(0,xs) = g(xs)
f(x,xs) = h(x,f(x/2,xs),xs) falls x>0


Fallunterscheidung: 

f = cond(g,h0,h1)

f(0,xs) = g(xs)
f(2x,xs) = h0(x,xs)
f(2x+2,xs) = h1(x,xs)

Man schreibt: f(x,xs) = match x with 
                           0 -> g(xs)
                         | S0(x) -> h0(x,xs)
                         | S1(x) -> h1(x,xs)


"Nachfolger":

S0(x) = 2x
S1(x) = 2x+1

Faktum: Mit Notationsrekursion, Fallunterscheidung, S0, S1, Konstanten
und Variablen ( = Projektionen) lassen sich alle primitiv rekursiven
Funktionen definieren. 

concat(0,y) = y
concat(S0(x),y) = S0(concat(x,y))
concat(S1(x),y) = S1(concat(x,y))

Abkuerzung fuer entsprechende Definition mit Rec und match. 

code(0) = 0
code(x) = concat(code(x/2),code(x/2))

succ(0) = S1(0)
succ(S0(x)) = S1(x)
succ(S1(x)) = S0(succ(x/2))

decode(0) = 0
decode(x) = succ(x/2)

Fuer decode(x) schreibt man auch |x|. decode(x) ist gerade die Laenge
der Binaerdarstellung von x. Es gilt |x|=decode(x)=[log_2(x+1)]. 

Man zeigt: ist f(x1..xn) primitiv rekursiv, so ist g(y1..yn) mit

g(code(x1),..,code(xn)) = code(f(x1,..,xn))

definierbar durch Notationsrekursion, Fallunterscheidung, ...

Abhilfe: 


Definition: Beschraenkte Notationsrekursion: 

f wird aus g,h,k durch beschraenkte Notationsrekursion definiert (f =
BRec(g,h,k)), wenn gilt: 

f(0,xs) = g(xs)
f(x,xs) = h(x,f(x/2,xs),xs) falls x>0

und ausserdem f(x,xs) <= k(x,xs)

Definition (Smash): 

x # y = 2^(|x|.|y|). 

Es gilt |x # y| = |x|.|y|, insbesondere |x#...#x| = |x|^n. 


Satz von Cobham: Die Klasse der in polynomialer Zeit berechenbaren
Funktionen auf natuerlichen Zahle n(in Binaerdarstellung) stimmt mit
der Klasse der Funktionen ueberein, die mit beschraenkter
Notationsrekursion, Fallunterscheidung, S0,S1,# definierbar sind. 

Beispiele: 

concat(x,y) ist auch durch beschraenkte Notationsrek definierbar, da
k(x,y)=x#y eine Schranke bildet. 

code(x) ist nicht durch beschraenkte Notationsrek definierbar, da man
leicht zeigt, dass zu jeder so definierbaren Funktion ein Polynom p
existiert, derart dass |f(xs)| <= p(|xs|).

Beweis des Satzes: Fuer die eine Richtung beweist man durch Induktion
ueber die Darstellung: Fuer alle Funktionen f(xs) aus Cobhams Klasse
existiert ein Polynom p sodass gilt: 

f(xs) ist in Zeit p(|xs|) berechenbar (und es gilt insbesondere
|f(xs)| <= p(|xs|)). 

Fuer die umgekehrte Richtung muss man zu gegebener deterministischer
Turingmaschine eine Funktion definieren (in Cobhams System), die einen
Schritt auf einer globalen Konfiguration durchfuehrt. Polynomial lange
Iteration dieser Ein-Schritt Funktion liefert dann die jede beliebige
PTIME Funktion. 

SICHERE REKURSION: 

Man teilt die Argumente einer Funktion in sichere und normale ein. Die
sicheren Argumente duerfen nur "sicher" verwendet werden (was das
heisst wird gleich gesagt). In der Notationsrekursion bestimmte Argumente
sicher sein. Genauer gesagt muessen rekursive Aufrufe ueber sichere
Argumente erfolgen. Auf der anderen Seite sind Argumente, ueber die rekurriert wird, immer als "normal" zu behandeln. 

Formal trennt man die normalen von den sicheren Argumenten durch ein
Semikolon: f(xs;ys) bedeutet: die xs sind normal, die ys sind sicher.

Die Funktionen des Systems BC sind nun wie folgt definiert. 

1) Die Projektionen f(xs;ys)=yi und f(xs;ys)=xi sind in BC. 
2) Die Konstante 0 und die Nachfolger S0(;x) und S1(;x) sind in BC (mit sicherem Argument). 

3) Sind f(xs;ys) und g1(us;) bis gn(us;) und h1(us;vs) bis hm(us;vs) in
BC, so auch f(g1(us;),...,gn(us;);h1(us;vs),...,hm(us;vs)). Sichere
Komposition. Intuition: Kein sicheres Argument darf normal benutzt
werden; will man einen Ausdruck in eine normale Position einsetzen, so
darf der nicht von sicheren Argumenten abhaengen. 

Komposition mit einer Projektion erlaubt es, ein Argument von "sicher"
auf "normal" herabzustufen. Heraufstufen geht aber nicht. 

4) Sind g(xs;ys) h0(xs;y,ys) h1(y,ys) in BC so auch 
   f=cond(g,h0,h1) gegeben durch 

   f(xs;0,ys) = g(ys)
   f(xs;2y,ys) = h0(xs;y,ys)
   f(xs;2y+2,ys) = h1(xs;y,ys)

   Fallunterscheidung ueber ein sicheres Argument ist erlaubt. 

5) Sind g(xs;ys) sowie h(x,xs;y,ys) in BC so auch f=rec(g,h) gegeben durch

   f(0,xs;ys) = g(xs;ys)
   f(x,xs;ys) = h(x,xs;f(x/2,xs;ys),ys) 

   Rekursion nur ueber normale Argumente, Verwendung des rekursiven
   Aufrufs nur ueber sichere Position.

Beispiele: 

concat(0;y) = y
concat(S0(x);y) = S0(;concat(x;y))
concat(S1(x);y) = S1(;concat(x;y))

Formal concat = rec(g,h) wobei g(;y)=y h(x;z,y)=u(;x,z) und 
       u=cond(g',h0,h1) wobei g'(z)=z, h0(;x,z)=S0(z), h1(;x,z)=S1(z). 

smash(0,x2;)=x2
smash(x1,x2;)=concat(x2;smash(x1/2,x2;))

|concat(x;y)| = |x| + |y|
|smash(x1,x2)| = |x1|.|x2|

Satz: ist f(xs) in FP, so existiert ein Polynom p, sowie eine
 BC definierbare Funktion h(z;xs) sodass gilt: 

|z| > p(|xs|) ==> h(z,xs) = f(xs) 

Korollar: ist f(xs) in FP, so kann f mit normalen Argumenten in BC
repraesentiert werden.

Satz: ist f(xs;ys) in BC repraesentierbar, so ist f in FP und es 
existiert ein Polynom p derart dass gilt |f(xs;ys)| <= p(|xs|)+max(|ys|). 

Korollar: BC=FP.


**********************************************************************

LFPL. 

Idee: Bellantoni-Cook: Falls 

Sei g(0,y) = y
g(t,y) = f(g(t/2,y))

und

|f(x)| <= |x| + c, 

dann 

|g(t)| <= c.|t| + |y|

Wenn jetzt aber 

h(0,y) = y
h(t,y) = g(h(t/2),0)

dann 

|h(t)| <= c^|t|

Daher muss die Funktion g als "nicht iterierbar" markiert
werden. Diese geschieht dadurch, dass das Argument t "nicht sicher"
ist. 

Diese drastische Massnahme verbietet aber alle geschachtelten
Iterationen und schliesst dadurch viele vernuenftige Algorithmen aus. 

LFPL liegt nun die Beobachtung zugrunde, dass eine Funktion, welche
die Laenge ueberhaupt nicht erhoeht, iteriert werden kann und das
Ergebnis dann wiederum diese Eigenschaft hat!

|f(x)| <= |x| 

dann g(|x|) <= |x| 


Man koennte immerhin noch erlauben 

|f(x)| <= |x| + 1

denn dann ist

|g(t,y)| <= |t| + |y| 

und somit

|h(t,y)| <= |y| 

Die Frage ist: wie kann man Funktionen, die die Laenge nicht, oder
hoechstens um Eins erhoehen durch syntaktische Methoden auszeichnen
ohne einerseits semantische Information einbringen zu muessen, wie bei
Cobham und andererseits ohne ueber Gebuehr restriktiv zu werden. 

LFPL ist eine funktionale Programmiersprache mit Booleans, Listen,
Baeumen in der die Invariante erhalten wird, dass alle definerbaren
Funktionen und Terme die Laenge nicht vergroessern. Hierbei ist
allerdings Laenge in einem geeigneten verallgemeinerten Sinne zu
verstehen, denn sonst koennte man ja nicht einmal die
Nachfolgerfunktionen S0, S1, oder das "cons" fuer Listen hinschreiben.

Zwei Prinzipien spielen eine Rolle. 

I) Die Laenge eines Paares (oder Records) ist die Summe (nicht das
   Maximum) der Laengen der Komponenten. 

II) Es gibt einen besonderen Typ <>, der nur ein Element enthaelt,
    welches die Laenge Eins besitzt. (Dieser Typ ist eher symbolisch
    zu verstehen, so wie void in Java). 

Schauen wir, wie wir cons typisieren koennen: 

(Die Laenge einer Liste ist definiert als ihre Laenge als Liste plus
die Summe der Laengen der Eintraege. Dieser Wert ist Null, wenn die
Eintraege Booleans sind, aber nicht Null wenn sie selber wieder Listen
sind.) 

cons : 'a * 'a list -> 'a list

|cons(x,y)| = 1 + |x| + |y| das ist nicht <= |x|+|y|. 

Aber wenn wir setzen: 

cons : <> * 'a * 'a list -> 'a list

dann haben wir 

|cons(d,x,y)| = 1 + |x| + |y| <= |d| + |x| + |y| 

da ja |d| = 1. 

Auf der anderen Seite ist 

nil : 'a list 

in Ordnung, da ja |nil()| <= 0 

Dies fuehrt zum dritten Prinzip: 

III) rekursive Konstruktoren von Datentypen bekommen ein extra Argument des
     Typs <>. 


Wie sieht es mit der Komposition aus? 

|f(x)| <= |x| und |g(x)| <= |x|, dann auch |f(g(x))| <= |x|. 

Aber wenn 

|f(x,y)| <= |x|+|y| 

und |g(x)| <= |x| und |h(x)| <= |x|, dann ist

|f(g(x),h(x))| <= 2.|x| !!!

Andererseits

|f(g(x), h(y))| <= |x| + |y|

Dies fuehrt zum Prinzip 

IV) Variablen duerfen in einem Term hoechstens einmal
    vorkommen. (Linearitaet). 

Analogie: f : V*V -> V bilineare Abbildung

       g(v) = f(v,v) ist keine lineare Abbildung. 

Ausnahme von IV. Variablen eines Typs, dessen Elemente Laenge 0 haben
duerfen mehrmals benutzt werden. Z.B. bool, aber nicht <>. 

Woher kommen Werte des Typs <>: Antwort Pattern-Matching.

Falls l : 'a list und g : 'b und h(d,x,y) : 'b

dann 

match l with nil -> g | cons(d,x,y) -> h(d,x,y) : 'b

Hierbei duerfen l, g, h auch noch andere Variablen enthalten (wie in
ML oder Java). Allerdings (Linearitaetsprinzip!) duerfen weder l und
g, noch l und h Variablen gemeinsam haben. g und h schon, denn es
kommt ja hoechstens eins von beiden zur Anwendung. 

Rekursion: Wir erlauben zunaechst beliebige rekursive Definitionen so,
wie in C. Ein Programm besteht also aus einer Menge gegenseitig
rekursiv definierter Funktionen. 

Definition: Sei L eine Programmiersprache mit Listen und Booleans. L
erfasst eine Komplexitaetsklasse C, wenn fuer alle A <= {0,1}^* gilt:
A ist in C genau dann, wenn die charakteristische Funktion von A als
Term vom Typ bool list -> bool in L darstellbar ist.

Theorem: LFPL mit beliebigen rekursiven Definitionen wie oben erfasst
die Komplexitaetsklasse LINSPACE. 

Schraenken wir auf strukturelle Rekursion ein, also etwa rekursive
Aufrufe nur auf kuerzeren Argumenten, so laesst sich die Laufzeit
polynomial beschraenken und man erhaelt: 

Theorem: LFPL mit nur struktureller Rekursion erfasst die Klasse der
in linearem Platz und gleichzeitig polynomieller Zeit loesbaren
Probleme. 

Nun kann man auch hoeherstufige Funktionen betrachten, also zu Typen
'a und 'b den Typ 'a->'b der Funktionen einfuehren. Hierbei bietet es
sich an, die Linearitaetsbeschraenkung auch hierauf auszudehnen;
insbesondere gilt so eine Funktion schon nach ihrer ersten Anwendung
als benutzt und darf dann nicht wieder verwendet werden. 

Theorem: LFPL mit Funktionstypen erfasst EXPTIME, LFPL mit
Funktionstypen, aber nur struktureller Rekursion erfasst P. 

Diese und weitere Ergebnisse finden sich in meinen Arbeiten zu
non-size increasing computation. 

A type system for bounded space and functional in-place update (Nordic
J. of Comp. 2000)

Linear types and non size-increasing polynomial time
computation. (Information & Computation 2003)

The strength of non size-increasing computation (Symp Princ. of
Prog. Lang. 2002)














Artikelaktionen


Funktionsleiste