Theoretische Informatik

NP ist unter Vereinigung und Durchschnitt abgeschlossen
Zeigen Sie, dass die Klasse NP unter Vereinigung und Durchschnitt abgeschlossen ist (siehe Satz 5.19).

nichtdeterministisches Python-Programm für 3-FARB
Geben Sie ein nichtdeterministisches Python-Programm an, das folgende Menge in Polynomialzeit akzeptiert (siehe Skript-Seite 319). Geben Sie die Laufzeit in O-Notation an.
3-FARB = {⟨G⟩ 􏰂􏰂 G ist ein 3-färbbarer, ungerichteter Graph}

Sum-of-Subset-Problem in NP
Zeigen Sie, dass folgende Menge die in Definition 5.16 genannten Eigenschaften erfüllt und deshalb in NP liegt.
SOS = {⟨a₁,...,a_m,b⟩􏰂􏰂m,a₁,...,a_m,b ∈ N und es existiert ein I ⊆ {1,...,m} mit 􏰃i∈I ai = b}

Polynomialzeit-Reduzierbarkeit
Zeigen Sie PARTITION ≤ SOS, indem Sie entsprechend der Definition 5.28 ein f : N → N angeben und nachweisen, dass f ∈ FP und ∀x ∈ N [x ∈ PARTITION ⇔ f(x) ∈ SOS].

Konkatenation und Regularität
Beweisen oder widerlegen Sie folgende Aussage für Sprachen L und K: Falls L ̸= ∅ und L, L · K ∈ REG, so ist auch K ∈ REG.

Reduktion von SOS auf PARTITION
Zeigen Sie SOS ≤ PARTITION indem Sie entsprechend der Definition 5.28 ein f : N → N angeben und nachweisen, dass f ∈ FP und ∀x ∈ N [x ∈ SOS ⇔ f(x) ∈ PARTITION].

Varianten von SOS

1. Unteraufgabe