# Übung 9 Aufgabe 1 - Simon Stadlinger, Jost Götte
##### a)
Es ist zu zeigen, dass das HamiltonPath Problem, also die Frage danach, ob ein Pfad in einem gegebenen Graphen $G$ existiert, der jeden Knoten nur einmal besucht, in NP ist.
Wir betrachten zur Lösung dieses Problems folgenden Algorithmus:

Wir wählen einen Startknoten, der einen im Graphen minimalen Grad $\geq 1$ hat, aus markieren diesen und branchen von diesem genau $n = |V|$ mal über die Anzahl seine Nachbarn. Dabei setzen wir den jeweiligen Nachbarn als Startknoten des neuen Branches und markieren ihn einmal. Wenn nach $n$ mal Branchen in einem Branch jeder Knoten genau einmal markiert wurde, geben wir 1 aus, ansonsten 0.

Wir wollen nun zeigen, dass dieses Programm das HamiltonPath Problem löst. Falls es einen Hamilton Weg gibt, so benötigt dieser genau $n$ Sprünge, da in jedem Sprung maximal ein neuer Knoten entdeckt werden kann. Wenn man mindestens einen Sprung mehr als $n$ macht, hat man zwangsläufig mindestens einen Knoten mehrmals besucht. Wenn man mindestens einen Sprung weniger als $n$ macht, hat man mindestens einen Knoten zu wenig besucht. Also entscheidet der Algorithmus richtig mit 1 also $G \in$ HamltonPath, wenn es mindestens einen Branches am Ende der $n$ verzweigungen gibt, sodass alle Knoten einmal markiert sind. Wenn dies nicht der Fall ist, ist mindestens ein Knoten doppelt markiert und ein Knoten gar nicht. Wenn das für alle Branches zutrifft, wird 0 also wie gewollt $G \notin$ HamiltonPath ausgegeben.

Es bleibt zu zeigen, dass dies in polynomieller Laufzeit möglich ist.
Den Startknoten mit dem kleinsten Knotengra $\geq 1$ zu finden ist in $\mathcal{O}(n)$ möglich. Anschließend wird $n$ mal gebranched mit (im Worst Case) $n-1$ neuen Branches. Somit liegt der nichtdeterministische Part in $\mathcal{O}(n^2)$. Das auswerten der Branches liegt in $\mathcal{O(n^3)}$, da für jeden der Branches einmal alle Knoten auf Markiertheit geprüft werden müssen. Somit liegt der Algorithmus in einer polynomiellen Zeit und das HamiltonPath Problem somit in NP.
##### b)
Es ist zu zeigen, dass $\leq_P$ eine Quasiordnung ist. Dafür ist zu zeigen, dass diese Relation reflexiv und transitiv ist.
Zunächst wird gezeigt, dass die Relation reflexiv ist. Es ist also zu zeigen, dass für alle Sprachen $L \in$ NP gilt:
Es gibt ein $f\in \mathcal{P}$ gibt welches in polynomieller Zeit terminiert, sodass
$$
\forall x: x\in L \iff f(x) \in L
$$
sei dieses $f$ nun die Identität. Diese gibt die Eingabe unverändert wieder zurück. Somit wird für alle x die Äquivalenz oben erfüllt und $f$ terminiert mindestens in polynomieller Zeit. Somit ist $\leq_P$ reflexiv.

Es bleibt zu zeige, dass $\leq_P$ transitiv ist. Es ist also zu zeigen, dass für drei Sprachen $A, B, C \in$ NP gilt:
$$
A\leq_P B\land B\leq_P C \Rightarrow A\leq_P C
$$
Es gelte also $A\leq_PB$ mit der Reduktionsfunktion $f$ und $B\leq_P C$ mit der Reduktionsfunktion $g$. Beide Reduktionsfunktionen sind polynomiell. Dann ist auch $h=f \circ g$ polynomiell, da nach Einsetzen einer Polynomiellen Funktion in eine andere Polynomielle Funktion wieder eine polynomielle Funktion entsteht. $h$ ist aber genau die Funktion, für die gilt:
$$
\forall x: x\in A \iff h(x) \in C
$$
somit ist $\leq_P$ auch transitiv und demnach eine Quasiordnung.