Komplexitätstheorie Hausaufgaben 8

Hausaufgabe 8.1

Sei C eine Klasse von Funktionen von und zu den natürlichen Zahlen inklusive 0. Wir sagen, dass C unter linker polynomieller Komposition abgeschlossen ist, wenn f(n) in C => p(f(n))=O(g(n)) für ein g(n) in C, für alle Polynome p(n). Wir sagen, dass C unter rechter polynomieller Komposition abgeschlossen ist, wenn f(n) in C => f(p(n))=O(g(n)) für ein g(n) in C, für alle Polynome p(n).

Intuitiv bedeutet die erstere (linke) Abgeschlossenheits-Eigenschaft, dass die entsprechende Komplexitätsklasse unabhängig vom Berechnungs-Modell ist, also robust bezüglich Änderungen im zugrundeliegenden Computer-Modell, dh es macht ihr nichts aus, ob man RAMs, einfache TM oder Multi-String-TM usw verwendet.

Hingegen bedeutet Abgeschlossenheit unter rechter polynomieller Komposition, dass die entsprechende Komplexitätsklasse abgeschlossen bezüglich Reduktionen ist.

Welche der folgenden Funktionenklassen sind unter linker polynomieller Komposition abgeschlossen, welche unter rechter? (^ bedeutet hier Exponentiation)

(a) {n^k: k>0}

(b) {n k: k>0}

(c) {k^n: k>0}

(d) {2^(n^k): k>0}

(e) {(log n)^k: k>0}

(f) {log n}

Hausaufgabe 8.2

Zeige, dass P unter Vereinigung und unter Intersektion abgeschlossen ist. Wiederhole für NP.

Hausaufgabe 8.3

Zeige mittels Abgeschlossenheit bezüglich einer bestimmten Operation, dass NP und SPACE(n) verschieden voneinander sind (wir wissen nicht, welches von den beiden das andere enthält).