Übungen zur Vorlesung Mathematische Logik SS 2008, Blatt 3

Aufgabe 7. Aus der Vorlesung wissen wir, daß die Menge aller Wörter über einem Alphabet Σ in der lexikographischen Ordnung R-aufzählbar sind. Sei r ≥ 1; geben Sie eine Ordnung auf der Menge (Σ^{∗})^{r} an, in der diese Menge R-aufzählbar ist.

Aufgabe 8. Sei f berechenbar mit df(f) ⊆ ℕ und bd(f) ⊆ ℕ. Zeigen Sie:

a) Falls f injektiv ist, so ist f^{−1} berechenbar.

b) Falls f monoton ist, so ist bd(f) entscheidbar. (Dabei heißt f monoton, falls f(k) ≤ f(l) für alle k, l ∈ ℕ mit k < l.)

Aufgabe 9.

Are we not drawn onward, we few, drawn onward to new era

Sei Σ = {0, 1}. Für ein Wort w = a_{1} … a_{|w|} ∈ Σ^{∗} sei w^{−1} = a_{|w|} … a_{1}. Ein Wort w ∈ Σ^{∗} ist ein Palindrom gdw. w = w^{−1}. Geben Sie ein nichtdeterministisches R-Programm an, das die Menge der Palindrome in Σ^{∗} entscheidet.

Aufgabe 10. Seien Σ und Π Alphabete und V ⊆ (Σ^{∗})^{r}, W ⊆ (Π^{∗})^{s} mit r, s ≥ 1. V heißt auf W polynomiell reduzierbar (V ≤_{p} W) gdw. es PTIME - Funktionen f_{1}, …, f_{s} von (Σ^{∗})^{r} nach Π^{∗} gibt, sodaß für alle r-Tupel x̄ ∈ (Σ^{∗})^{r} gilt:

x̄ ∈ V ⟺ (f_{1}(x̄), f_{2}(x̄), …, f_{s}(x̄)) ∈ W.

Sei Γ ein weiteres Alphabet und U ⊆ (Γ^{∗})^{t} für ein t ≥ 1. Zeigen Sie:

1. Ist U ≤_{p} V und V ≤_{p} W, so ist U ≤_{p} W.

2. Ist V ≤_{p} W und W ∈ PTIME, so ist V ∈ PTIME.

3. Ist V ≤_{p} W und W ∈ NPTIME, so ist V ∈ NPTIME.

W ⊆ (Π^{∗})^{s} heißt NP-vollständig gdw. W ∈ NPTIME und für alle V ∈ NP gilt V ≤_{p} W. Folgern Sie:

PTIME = NPTIME ⟺ W ∈ PTIME.

Aufgabe 11. Sei W ⊆ ℕ und a, b ∈ ℕ mit a, b ≥ 2. Zeigen Sie für W_{a} := {[n]_{a} | n ∈ W } und W_{b} := {[n]_{b} | n ∈ W }, daß W_{a} ∈ PTIME gdw. W_{b} ∈ PTIME.

Abgabe: Mittwoch, 21. Mai 2008, vor der Vorlesung.