# Übung 10 Aufgabe 1 - Simon Stadlinger, Jost Götte
#### b)
Es ist zu zeigen, dass das Problem $3-SAT$ in $NP$ ist. Dieses Problem ist definiert als die Menge aller erfüllbaren aussagenlogischen Formeln in konjunktiver Normalform mit je genau drei Literalen pro Klausel. Gegeben sind also $m$ Mengen der Größe 3 mit Elementen aus $\{x_i, x_i\mid i\leq n\}$. Die dadurch repräsentierte aussagenlogische Formel ist erfüllbar genau dann, wenn es eine Belegung der Variablen $\{x_i\mid i\leq n\}$ gibt, sodass jede der $m$ Klauseln mindestens ein wahres Literal enthält.

Es wird nun ein np-Algorithmus angegeben, der dieses Problem löst. Zur Eingabe der $m$ Klauseln wählt er nichtdeterministisch für jede Variable eine Belegung aus $\{0,1\}$. Anschließend wird geprüft, ob jede Klausel mindestens eine Belegung hat, die sie wahr werden lässt. Sollte das bei keiner Variablenbelegung der Fall sein wird $false$ ausgegeben, ansonsten $true$.

Der Algorithmus läuft in Polynomialzeit, da die Variablengelegung in $\mathcal{O}(n)$ erfolgt und die Auswertung der eingesetzten Formeln in $\mathcal{O}(m)$.

Der Algorithmus entscheidet für eine gegebene Instanz von 3-SAT korrekt, weil nichtdeterministisch auf jeden Fall eine Variablenbelegung gefunden wird, für die die Aussage wahr wird, wenn es sie denn gibt. Das Prüfen sorgt dafür, dass diese Belegung auch erkannt wird und richtigerweiße $true$ zurückgegeben wird. Ansonsten gibt es stehts mindestens eine Klausel, für die die Variablenbelegung $false$ ergibt und es wird $false$ zurückgegeben.

Somit ist der Algorithmus korrekt und $3-SAT \in NP$
#### a)
Es ist zu zeigen, dass das Problem $SubsetSUM$ in $NP$ ist. Das Problem fragt danach, ob es zu einer gegebenen Menge $S$ an Zahlen aus $\mathbb{Z}$ und einer Zielsumme $s\in \mathbb{Z}$ eine Teilmenge der gegebenen Zahlen gibt, deren Summe genau $s$ ist.

Es wird nun ein np-Algorithmus angegeben, der dieses Problem löst. Aus der Eingabe der Menge von ganzen Zahlen wird nichtdeterministisch eine Teilmenge ausgewählt und anschließend aufsummiert. Wenn diese Summe gleich der Zielsumme ist wird $true$ zurückgegeben, ansonsten wieder verworfen.

Der Algorithmus läuft in Polyzeit, da eine Teilmenge von Zahlen aus $S$ und im Anschluss ihre Summe in $\mathcal{O}(|S|)$ gefunden werden kann. Der anschließende Vergleich mit $s$ ist konstant.

Es wird nun gezeigt, dass der Algortihmus für eine gegebene Instanz von $SubsetSUM$ korrekt entscheidet. Wenn für diese eine Teilmenge existiert, sodass die Zielsumme erreicht wird, wird diese Teilmenge durch den Algorithmus nichtdeterministisch gefunden. Durch den Vergleich am Ende mit $s$ wird diese Teilmenge auch erkannt und in diesem Fall $true$ zurückgegeben. Wenn es keine Teilmenge gibt, kann der Algorithmus keine finden und gibt $false$ zurück.

Somit ist der Algorithmus korrekt und $SubsetSUM\in NP$.