u13.tex

\include{headerueb}
\include{header}
\include{info}


\newcommand{\nr}{13}

\begin{document}
\section*{Aufgabe 1}

\section*{Aufgabe 2}
\paragraph{a) 0-1-LP} $ $

Sei $n$ die Anzahl der Variablen und $m$ die Anzahl der Nebenbedingungen und
bezeichne $x_i$ ($i=1,\ldots,n$) die Variablen des Programms,
$f(x) = a_1 x_1 + a_2 x_2 + \cdots + a_n x_n$ die zu minimirende Funktion
$N_j: a_{j,1} x_{i_{j,1}} + a_{j,2} x_{i_{j,2}} + \cdots + a_{j,n_j} x_{i_{j,n_j}} \geq B_j$
bezeichne die Nebenbedinung $j$.

Das Progamm wird durch $a_1\#\cdots\#a_n\#\#N_1\#\#N_2\#\#\cdots\#\#N_3$ codiert,
wobei $N_j$ durch $a_{j,1}\#i_{j,1}\#\cdots\#a_{j,n_j}\#i_{j,n_j}$ codiert wird und 
alle Variablen in Binaerdarstellung codert werden.

Bezeichen $l$ die Laenge dieser Codierung. 
Es gilt $l = \Omega(n + m + \log(\sum a_i + \sum a_{j,i}))$

\begin{description}
\item[0-1-LP $\in NP$]

\begin{eqnarray}
L &=& \{ \langle LP \rangle: \text{ das lineare Program $LP$ ist erfuellbar} \}  \\
x &=& b_1, b_2, \cdots, b_n \text{, $b_i \in \{0,1\}$ eine belegung fuer $x_i$}
\end{eqnarray}

Fuer die Codierung von $x$ reicht fuer jede Variable in $LP$ ein Bit aus. Also 
ist $|x| = O(n)$

\begin{alltt}
algorithm \(A(LP,x)\)
    for \(j = 1 \cdots m\)
       \(b=0 \)
       for \(k = 1 \cdots n_j\)
          if \(b\sb{i\sb{j,k}} = 1\)
             \(b = += a\sb{j,i\sb{k}}\)
       if \(b > B\sb{j}\)
          return false
    return true
\end{alltt}

Durch den Schleifendurchlaefe wurd auf jedes der $a_{j,i_{k}}$ nur einmal zugegriffen
und diese zu auf $b$ summiert. Da diese Zahlen auch in der Eingable codiert sind,
kann dies Summe sowie der weitere Vergleich mit $B_j$ in $O(l^2)$ berechnet werden.

Also liegt 0-1-LP in NP


\item[0-1-LP ist NP-schwer:] Reduktion von 3-SAT auf 0-1-LP
\begin{eqnarray}
f &:& \{\text{3-CNF}\} \to \{\text{0-1-LP}\} \\
  && (I,B) \mapsto LP
\end{eqnarray}
Dabei wird durch $I$ und $B$ wie folgt die CNF mit $p$ variablen und $o$ Klauseln angegeben:\\
In $I = i_{11},i_{12},i_{13}, i_{21}, i_{22}, i_{23}, \cdots, i_{o1}, i_{o2}, i_{o3}$
werde die Indizes der Variablen in den Literalen angegebn und in
und in $B = b_{11},b_{12},b_{13}, b_{21}, b_{22}, b_{23}, \cdots, b_{o1}, b_{o2}, b_{o3}$,
ob diese negiert sind:
$i_{ij} \in \{1,\cdots,p\}$ gibt den Index der Variable des $j$. Literals in der $i$. Klausel an,
$b_{ij} \in \{0,1\}$, ob diese negiert vorkommt (0) oder nicht (1).

Das lineare Programm wird mit $2p$ Variablen konstruiert,
wobei fuer jeden Variable $y_i$ der CNF eine Variable fuer $x_i$ und eine Variable $\bar{x}_i$
eingefuert wird, die $y_i$ bzw $\lnot y_i$ entsprechen.

Aus den Klauseln werden Nebenbedinungen der Form $-\dot x_{i_1} - \dot x_{i_2} - \dot x_{i_3}\leq -1$ konstroiert,
wobei $i_1, i_2, i_3$ den Indizes der Variablen in der Klausel entsprechen und
$\dot x$ entsprechend der $b_{ij}$ in der Klausel entweder die Variable $x$ oder die Variable $\bar x$ ist.

Zusaetzlich muss fuer jede der Variablen der CNF eine Nebenbedinung eingefuehrt werden,
die Verhindert dass $x_i$ und $\bar x_i$ die gleiche Belegung bekommen:
$x_i + \bar x_i = 1$. Diese Bedinung kann durch zwei Bedinungen in Standartnormalform umgeformt werden.

Dadurch koennen die Nebenbedinungen nur erfuellt werden, wenn auch alle Klauseln in CNF erfuellbar sind:

Die Nebenbedingungen fuer jede Variable koennen insgesamt in $O(p)$ konstruiert werden.
Die Nebenbedingungen pro Klausel sind nur ein Umformung der CNF-Codierung und kann
auch in lineare Zeit berechnet werden.

\item[CNF erfuellbar $\Rightarrow$ LP erfullbar] $ $

Sei $y_i$ mit $i=1 \cdots p$ die Belegung der Variablen in CNF,
dann ist $x_i = y_i$, $\bar x_i = \lnot y_i$ auch ein gueltige Belegung fuer $LP$.

Fuer die den Klauseln entsprechenden Nebenbedinungen muss mindestens eine
der Variablen $\dot x = 1$ sein, da ansonsten die Klausel nicht erfullt waere.

Durch die gewahlte Belegung  $x_i = y_i$, $\bar x_i = \lnot y_i$ ist auch stets gewahert,
das entweder $x_i$ oder $\bar x_i$ 1, die andere 0 ist, sodass derene Summe stest $1$ ergibt.
Also sind auch die restlichen Nebenbedinungen erfuellt.

\item[CNF erfuellbar $\Leftarrow$ LP erfuellbar] $ $
Sind die Nebenbedingungen in $LP$ erfuellbar, so muss auch mindestens ein Literal in jeder 
Klausel erfuellbar sein, da sonst in der Bedinung $-\dot x_{i_1} - \dot x_{i_2} - \dot x_{i_3}\geq -1$
ist.

\qed

\end{description}


\paragraph{b) ILP ist NP-schwer} Reduktion von 0-1-LP auf ILP
\begin{eqnarray}
f &:& \{\text{0-1-LP}\} \to \{\text{ILP}\} \\
  && LP \mapsto LP'
\end{eqnarray}

Wobei $LP'$ $LP$ entahelt, nur fuer jeden Variable $x$ in $LP$
zwei weiteren Nebenbedingungne einfuehrt, die dafuer sorgen,
dass $x \in \{0,1\}$:
Fuer jede Variable $x$ werden die Nebenbedingungen $-x \leq 0$ und $x \leq 1$
hinzugefuegt.

Die ist in linearer Zeit bezueglich der Anzahl der Variablen moeglich.
\begin{description}
\item[$LP$ erfuellbar $\Rightarrow$ $LP'$ erfuellbar]
Falls $LP$ erfullbar ist, ist auch die gleiche Loesung eine gueltige Loesung fuer $LP'$,
da die neuen Nebenbedingungen durch Variablen mit Belgung in $\{0,1\}$ immer erfuellt sind
und alle anderen Nebenbedingugen auch Teil von $LP$ sind.

\item[$LP'$ erfuellbar $\Rightarrow$ $LP$ erfuellbar] $ $

\begin{enumerate}
\item Die Belegungen koennen nur Werte aus $\{0,1\}$ enthalten:

    Falls eine Belegung fuer $x$ nicht aus $\{0,1\}$ ist,
    ist eine der Bedingungen $-x \leq 0$ und $x \leq 1$ nicht erfullt,
    also kann dies keine gueltige Belegung sein.

    Desshalb kann die Belegung von $LP'$ auch fuer $LP$ verwendet werden.

\item Die Belegnung erfullt auch $LP$

    Da alle Nebenbedingugne von $LP$ auch in $LP'$ enthalten sind,
    muessen diese von der Belegung erfullt werden, also wird $LP$ auch von der Belegung erfuellt.

\end{enumerate}

\end{description}

\paragraph{c) vollstanidg?} 
Der Beweis fuer fuer die Vollstaendigkeit ist nicht so einfach, 
da der Zeuge, also die Belegung der Variablen nun auch grosse Zahlen enthalte
kann, sodass die Lanege des Zeuges nicht polynomiell zu der Laenge der 
Eingabe ist.

\paragraph{d) QNP ist NP-schwer} Redukjtion von 0-1-LP auf QLP

Nebenbedingungen <+ $x^2 - x = 0$ +>
\begin{eqnarray}
f &:& \{\text{0-1-LP}\} \to \{\text{QLP}\} \\
  && LP \mapsto LP'
\end{eqnarray}

Wobei $LP'$ $LP$ entahelt, nur fuer jeden Variable $x$ in $LP$
eine weiteren Nebenbedingungne einfuehrt: $x^2 - x = 0$

Die ist in linearer Zeit bezueglich der Anzahl der Variablen moeglich.

\begin{description}
\item[$LP$ erfuellbar $\Rightarrow$ $LP'$ erfuellbar]
Falls $LP$ erfullbar ist, ist auch die gleiche Loesung eine gueltige Loesung fuer $LP'$,
da die neuen Nebenbedingungen durch Variablen mit Belgung in $\{0,1\}$ immer erfuellt sind
und alle anderen Nebenbedingugen auch Teil von $LP$ sind.

\item[$LP'$ erfuellbar $\Rightarrow$ $LP$ erfuellbar] $ $

\begin{enumerate}
\item Die Belegungen koennen nur Werte aus $\{0,1\}$ enthalten:

    Falls eine Belegung fuer $x$ nicht aus $\{0,1\}$ ist,
    ist eine der Bedingungen $x^2 - x = 0$ nicht erfullt, 
    da diese Gelichung nur die Loesung $x=0$ oder $x=1$ besitzt.

    Desshalb kann die Belegung von $LP'$ auch fuer $LP$ verwendet werden.

\item Die Belegnung erfullt auch $LP$

    Da alle Nebenbedingugne von $LP$ auch in $LP'$ enthalten sind,
    muessen diese von der Belegung erfullt werden, also wird $LP$ auch von der Belegung erfuellt.

\end{enumerate}
\end{description}


\section*{Aufgabe 3}
\begin{description}
\item[ungerichteter HAM $\in$ NP]

\begin{eqnarray}
L &=& \{ \langle G \rangle: \text{ungerichteter Graph $G$ hat HAM-Kreis} \}  \\
x &=& v_1,v_2,\cdots,v_n
\end{eqnarray}

\begin{alltt}
algorithm \(A(G,x)\)
    if \(x\) besteht nicht aus \(|V|\) Knoten
        return false
    // Ueberpruefe ob Knoten nur einfach in \(x\) 
    for \(i = 1 \cdots n\)
        for \(j = 1 \cdots n\)
            if \(i\neq j \land v_i = v_j\)
                return false
    // Ueberpruefe ob Kanten aus zuegen im Graph
    for \(i = 1 \cdots n-1\)
        if \((v\sb{i},v\sb{i+1}) \notin E\)
            return false
    if \((v\sb{n},v\sb{1}) \notin E\)
        return false

    return true
\end{alltt}

Die Scheifendurchlauefe brauche jeweils nur Durchlauefe $O(|V|^2)$,
also ist $A$ polynomiell.


\item[ungerichteter HAM NP-shwer] Reduktion von gerichtetem HAM auf ungerichteten

\begin{eqnarray}
f &:& \{\text{gerichtete Graphen}\} \to \{\text{ungerichtete Graphen}\} \\
  && G=(V,E) \mapsto G'=(V',E')
\end{eqnarray}

Wobei $V' = V\times \{0,1,2\}$ und 
$E' = \{ ( (v,0), (v,1) ) | v \in V \} \cup
      \{ ( (v,1), (v,2) ) | v \in V \} \cup 
      \{ ( (v,2), (w,0) ) | (v,w) \in E \}$

Dies kann in linearer Zeit konstroiert werden: Fuer $V'$ und die ersten beiden Teilmenge aus $E'$
muessen nur die Knoten vervielfaeltigt werden, fuer die letzte teilemenge der Kanten, muss 
nur jedes Element aus $E$ veraendert werden.

\item[gerichteter HAM-Kreis in $G$ $\Rightarrow$ ungerichteter HAM-Kreis in $G'$] $ $

Sei $K = v_1 \to v_2 \to \cdots \to v_n$ der HAM-Kreis in $G$.
Dann ist $K' = (v_1,0) \to (v_1,1) \to (v_1,2) \to (v_2, 0) \to (v_2, 1) \to \cdots \to (v_n,2)$
HAM-Kreis in $G'$:

Da $K$ alle Knoten in $G$ genau einmal enthaelt und in $K'$ fuer jeden Knoten $v$ $(v,0)$, $(v,1)$ und $(v,2)$ enthalten sind,
wird auch in $K'$ jeder Knoten genau einmal Besucht.

Da in $G$ die Kanten $v_i \to v_{i+1}$ und $v_n \to v_0$ existieren,
   sind nach Konstruktion auch die Kanten $(v_i,0) \to (v_i,1) \to (v_i,2) \to (v_{i+1},0)$ und
   $(v_n,0) \to (v_n,1) \to (v_n,2) \to (v_1,0)$ enthalten.
   \qed


\item[ungerichteter HAM-Kreis in $G'$ $\Rightarrow$ gerichteter HAM-Kreis in $G$]

Obda faengt der Kreis bei einem Knoten $(v_1,0)$ an. Da der Kreis $(v_1,1)$ enthalten muss,
und $(v_1,0)$ nur einmal enthalten sein darf, muss die Kante $((v_1,0),(v_1,1)$ auf dem Kreis
vor oder hinter $(v_1,0)$ liegen. Da der Kreis ungerichet ist, flogt obda $(v_1,1)$ in dem Kreis auf $(v_1,0)$.
Darauf muss nun $(v_1,2)$ folgen, da dies der einzige Weg von $(v_1,1)$ zu einem unbesuchten Knoten ist.
Nach Konstruktion gehen von dem Knoten $(v_1,2)$ nur Kanten zu Knoten der vorm $(\cdot,0)$. 

Bezeichne $(v_2,0)$ den Knoten, der auf dem HAM-Kreis auf $(v_1,2)$ folgt. Fuer diesen Knoten
ergeben sicht wie fuer $(v_0,0)$, dass $(v_1,1)$ und $(v_1,2)$ folgen, gefolgt von dem naechsten 
knoten $(v_2,0)$. \ldots

Also muss der HAM-Kreis folgende Form haben: 
$(v_1,0) \to (v_1,1) \to (v_1,2) \to (v_2,0) \to (v_2,1) \to \cdots \to (v_n,0) \to (v_n,1) \to (v_n,2)$

Da $(v,2) \to (w,0)$ nur aus einer Kante $(v,w)$ in $V$ entstanden sein kann,
ist $v_1 \to v_2 \to \cdots \to v_n$ ein HAM-Kreis in $G$.

\end{description}

\end{document}