\documentclass[10pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 6 \\
        Übungsgruppe 7 - Mi, 16-18 Uhr \\
        Elena Kvassova}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
        Dirk Heine (Matrikelnummer 2030941)}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}

\maketitle

\newpage

\section*{Aufgabe 2}
Die zu beweisende Implikation lässt sich auch durch einen äquivalenten Ausdruck darstellen
\begin{eqnarray*}
    L_1 \in P & \Rightarrow & L_1 \le_p L_2 \\
    \Longleftrightarrow\quad (L_1 \not\in P) & \vee & (L_1 \le_p L_2)
\end{eqnarray*}
Wir beweisen die Aussage durch einen Widerspruchsbeweis. Dazu negieren wir die
Aussage und suchen ein Gegenbeispiel. Wenn wir ein Gegenbeispiel finden, muss
die behauptete negierte Aussage falsch sein und somit die ursprüngliche 
Aussage richtig sein. Behauptung für Widerspruchsbeweis:
\begin{eqnarray*}
    && \overline{(L_1 \not\in P) \vee (L_1 \le_p L_2)} \\
    \Longrightarrow && \overline{(L_1 \not\in P)} \wedge \overline{(L_1 \le_p L_2)} \\
    \Longrightarrow && (L_1 \in P) \wedge (L_1 \not\le_p L_2)
\end{eqnarray*}
Wähle ein beliebiges $L_1 \in P$, jedoch mit $L_1\neq\varnothing$ und
$L_1\neq\Sigma^*$. Setze $L_2=L_1$. Es ist offensichtlich, dass
$L_1$ mit der Identitätsfunktion $f(w)=w$ in polynomieller Zeit auf $L_2$
reduzierbar ist. Somit ist bereits ein Gegenbeispiel zur Behauptung
des Widerspruchsbeweises gefunden und die Aussage in der Aufgabe muss wahr sein. \QED

\section*{Aufgabe 3}
\begin{enumerate}[(a)]
    \item   Für einen gegebenen DHC $v_1,\ldots,v_n$ auf $G=(V,E)$ sei $f(G,v_i)=(G',v'_i)$ mit
            $$ G' = (V,E') \text{ mit } E' = E \backslash \{(v_1,v_2)\} \text{ und} $$    
            $$ v'_i = \begin{cases} v_{i-1} & \text{für } i \ge 2 \\ v_n & \text{für } i=1 \end{cases} $$
            gegeben. Die Funktion $f$ ist offensichtlich in polynomieller Zeit berechenbar.
            
            Den \textbf{Sonderfall}, dass für die Eingabe $w$ in $E$ die Kante von Knoten $v_1$ nach $v_2$ nicht existiert,
            also $(v_1,v_2) \not\in E$, betrachten wir an dieser Stelle gesondert. In diesem
            Fall ersetzen wir die Funktion $f$ durch die Identität, setzen also $v'_i=v_i$ und
            $E'=E$. Es ist klar, dass unter der Voraussetzung $(v_1,v_2) \not\in E$
            $w$ kein DHC sein kann (die Implikation ,,$w \in L_1 \Longrightarrow\ldots$`` muss nicht
            bewiesen werden, da die Voraussetzung nie wahr sein kann) und dass $f(w)$ kein
            DHP sein kann (die Implikation ,,$\ldots\Longleftarrow f(w) \in L_2$`` muss nicht
            bewiesen werden, da die Voraussetzung nie wahr sein kann). Damit ist die
            Äquivalenz für diesen Sonderfall gezeigt. In der übrigen Betrachtung
            wird dieser Sonderfall nicht mehr berücksichtigt und es wird angenommen,
            dass $(v_1,v_2) \in E$ gilt.
            
            Zeigen zunächst die \textbf{Implikationsrichtung} $\mathbf{w \in L_1 \Longrightarrow f(w) \in L_2}$.
            Wenn $w \in L_1 = $ DHC gilt, dann gilt $(v_i,v_{i+1}) \in E \:\forall 1 \le i < n$
            und $(v_n,v_1) \in E$. Nach Anwendung der Funktion $f$ existieren mindestens
            noch die Kanten $(v_i,v_{i+1}) \in E' \:\forall 2 \le i < n$ und $(v_n,v_1) \in E'$,
            es gilt jedoch auf jeden Fall $(v_1,v_2) \not\in E'$. In Hinblick auf
            die neue Nummerierung existieren mindestens die Kanten
            $(v'_i,v'_{i+1}) \in E' \:\forall 1 \le i < n-1$ und $(v'_{n-1},v'_n) \in E'$.
            Es gilt also $(v'_i,v'_{i+1}) \in E' \:\forall 1 \le i < n$. Somit liegt ein DHP
            vor und es gilt $f(w) \in L_2 = $ DHP.
            
            Zeigen jetzt die \textbf{Implikationsrichtung} $\mathbf{w \in L_1 \Longleftarrow f(w) \in L_2}$.
            Wenn $f(w) \in L_2 = $ DHP gelten soll, müssen mindestens die Kanten
            $(v'_i,v'_{i+1}) \in E' \:\forall 1 \le i < n$ existieren. Diese Kanten
            entsprechen vor der Transformation den Kanten
            $(v_i,v_{i+1}) \in E \:\forall 2 \le i < n$ und $(v_n,v_1) \in E$.
            Nehmen wir die Kante $(v_1,v_2) \in E$ die wir durch die Funktion $f$
            explizit entfernt haben (und die nach Ausschluss des obigen Sonderfalls existiert
            haben muss) hinzu, so wissen wir nun, dass die Kanten
            $(v_i,v_{i+1}) \in E \:\forall 1 \le i < n$ und $(v_n,v_1) \in E$
            existieren. Damit haben wir einen DHC und es gilt $w \in L_1 = $ DHC.
            
            Aus $w \in L_1 \Longrightarrow f(w) \in L_2$ und $w \in L_1 \Longleftarrow f(w) \in L_2$
            folgt $w \in L_1 \Longleftrightarrow f(w) \in L_2$. Somit ist $L_1 \le_p L_2$
            und DHC $\le_p$ DHP. In Verbindung mit dem oben bewiesenen Sonderfall ist die Aussage allgemeingültig. \QED
    \item   Sei ein DHP $v_1,\ldots,v_n$ auf $G=(V,E)$ gegeben. Um einen
            DHC zu erhalten müssen wir lediglich noch die Kante $(v_n,v_1)$
            in den Graphen aufnehmen, sofern diese noch nicht existiert.
            Das Hinzufügen einer Kante ist trivialerweise in polynomieller Zeit realisierbar.
            Ein DHC ist also $v'_i=v_i \:\forall i$ auf $G'=(V,E')$ mit
            $E'=E\cup\{(v_n,v_1)\}$. Damit ist die Implikationsrichtung
            $w \in L_1 \Longrightarrow f(w) \in L_2$ gezeigt. Die umgekehrte Implikation
            $w \in L_1 \Longleftarrow f(w) \in L_2$ ist ebenfalls trivial, da unter
            der Voraussetzung $f(w) \in L_2 = $ DHC die Kanten
            $(v_i,v_{i+1}) \in E' \:\forall 1 \le i < n$ und $(v_n,v_1) \in E'$
            existieren müssen und wir höchstens die Kante $(v_n,v_1)$ eingefügt haben
            und somit $E$ mindestens die Kanten $(v_i,v_{i+1}) \in E \:\forall 1 \le i < n$
            enthalten muss. Dies reicht bereits aus, um einen DHP zu haben.
            Somit ist DHP auf DHC reduzierbar und es gilt DHP $\le_p$ DHC. \QED
\end{enumerate}

\section*{Aufgabe 4}
\begin{enumerate}[(a)]
    \item   Eine Disjunktion von Monomen ist immer dann erfüllbar, wenn
            mindestens ein Monom erfüllbar ist. Ein Monom ist offensichtlich
            genau dann erfüllbar, wenn kein Literal sowohl in der nicht-negierten
            als auch in der negierten Form in dem Monom auftritt. Die
            Prüfung der Erfüllbarkeit eines Monoms ist trivial in linearer
            Zeit $\OnotO(n)$ realisierbar. Somit ist die Prüfung der Erfüllbar
            der Disjunktion ebenfalls in linearer Zeit $\OnotO(m \cdot n)$
            realisierbar. \QED
    \item   Nach den Sätzen von De Morgan gilt, dass die Negation einer
            Disjunktion von Monomen (aus unserem Problem) eine Konjunktion
            von Co-Monomen ist (ein Co-Monom ist eine Disjunktion von Literalen).
            Zum Beispiel ist
            $$ \overline{x_1x_3\overline{x_4} \vee \overline{x_1}x_2x_4} = \left( \overline{x_1}\vee\overline{x_3}\vee x_4 \right) \wedge \left( x_1\vee\overline{x_2}\vee\overline{x_4} \right) $$
            Damit läßt sich unser Problem, eine Variablenbelegung $a\in\{0,1\}^n$
            zu finden, so dass die Disjunktion von Monomomen gleich 0 ist,
            auf die Suche einer Variablenbelegung $a\in\{0,1\}^n$, so dass
            eine Konjunktion von Co-Monomen gleich 1 ist, überführen.
            Dass dieses Problem NP-vollständig ist, wurde durch den
            \emph{Satz von Cook} bereits bewiesen, so dass auch unser
            Problem NP-vollständig ist. \QED
\end{enumerate}

\section*{Aufgabe 5}
\begin{enumerate}[(a)]
    \item   Beweis-Konstruktion analog zum Beweis von Satz 3.4.2 zum Cliquen-Problem.
            Sei $C=(c_1,\ldots,c_m)$ mit $c_i=z_{i1} \wedge z_{i2} \wedge z_{i3}$ und
            $z_{ij}\in\{x_1,\overline{x_1},\ldots,x_n,\overline{x_n}\}$ eine Eingabe
            für das ,,negierte 3-SAT-Problem``.
            
            Unter dem ,,negierten 3-SAT-Problem`` verstehen wir das Problem der
            \emph{Nicht-}Erfüllbarkeit einer Disjunktion von Co-Monomen (jeweils
            bestehend aus der Konjunktion von drei Literalen). Dieses Problem
            lässt sich trivial auf das reguläre 3-SAT-Problem überführen.
            
             Die Eingabe $f(C)=(G,k)$ mit $G=(V,E)$ für das Independent-Set-Problem (IP)
             soll folgendermaßen aussehen. $V$ enthält $3m$ Knoten $(i,j), 1 \le i \le m, 1 \le j \le 3$,
             die die Literale in den Klauseln darstellen. $E$ enthält die Kante
             zwischen $(i,j)$ und $(i',j')$, wenn $i=i'$ ist (es handelt sich um Knoten
             aus den \emph{gleichen} Klauseln) und $z_{ij} \neq \overline{z}_{i'j'}$ ist
             (die Literale können gleichzeitig erfüllt sein). Schließlich sei $k=m$.
             Natürlich ist $f$ in polynomieller Zeit berechnenbar.
             
             Sei nun $a$ eine Belegung, die \emph{keine} Klausel erfüllt. Dann ist in
             jeder Klausel mindestens ein Literal \emph{nicht} erfüllt. Wir betrachten
             die zugehörigen $m$ Repräsentanten in $G$. Der Graph $G$ enthält auf ihnen
             ein Independent Set, da die Literale nicht aus den gleichen Klauseln
             kommen und gleichzeitig erfüllt sind.
             
             Wenn $G$ andererseits ein Idependent Set der Größe $m$ enthält, müssen die
             Knoten des Independent Set Literale aus verschiedenen Klauseln repräsentieren.
             Darüber hinaus ist es \emph{nicht} möglich, eines dieser Literale zu
             erfüllen. Die Klauselmenge $C$ ist also erfüllbar und damit ist IP NP-vollständig. \QED
    \item    Das Vertex-Cover-Problem (VC) lässt sich auf IP überführen.
             Die Menge $V \backslash V'$ enthält alle Knoten, die von keiner Kante aus $E$
             berührt werden, und möglicherweise weitere Knoten. Diese weiteren Knoten
             sind offensichtlich \emph{nicht} durch Kanten mit Knoten aus $V \backslash V'$
             verbunden (eine Kante verbindet immer genau zwei Knoten; nach Voraussetzung
             muss sich mindestens einer der beiden Knoten in $V'$ befinden; somit
             können nicht beide in $V \backslash V'$ sein, da ein Knoten nicht gleichzeitig
             in $V'$ und $V \backslash V'$ enthalten sein kann, da $V \cap (V \backslash V') = \varnothing$).
             
             Es ist klar, dass $V \backslash V'$ ein Idependent Set darstellt, da es
             wie oben gezeigt keine Kanten zwischen zwei Knoten aus dieser Menge gibt.
             In Aufgabenteil~(a) haben wir bereits gezeigt, dass das IP NP-vollständig
             ist. Da sich $V'$ aus $V$ und $V \backslash V'$ bestimmen lässt, ist auch
             VC NP-vollständig. \QED
\end{enumerate}

\end{document}
