\documentclass[12pt]{article}

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

\thispagestyle{empty}

\title{Theoretische Informatik (WS 2005/2006) - Übungsblatt 12}
\author{Jan Hendrik Dithmar - Matrikelnummer 2031259 \\
		Do, 11-13 Uhr, Vasileios Anastasatos
	}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetC}{\ensuremath{\mathbb{C}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\SetB}{\ensuremath{\mathbb{B}}}
\newcommand{\R}{\ensuremath{\mathbb{R}}}
\newcommand{\N}{\ensuremath{\mathbb{N}}}
\newcommand{\C}{\ensuremath{\mathbb{C}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Q}{\ensuremath{\mathbb{Q}}}
\newcommand{\B}{\ensuremath{\mathbb{B}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}
\newcommand{\OnotO}{\ensuremath{\mathcal{O}}}
\newcommand{\eur}{\mbox{\euro}}
\newcommand{\bild}[4]{
	\begin{figure}[htpb]
		\centering
			\includegraphics[width=#1cm]{#2}\\[0.2cm]
			\caption{#3}
			\label{#4}
	\end{figure}
	}

\maketitle

\newpage
\section*{Aufgabe 1}
Um zu zeigen, dass \textsf{SMERF} \textsf{NP}-vollständig ist, muss man zeigen, dass \textsf{SMERF} sowohl \textsf{NP} ist, als auch, dass es \textsf{NP}-vollständig ist.
\begin{enumerate}
	\item \textsf{SMERF} ist in \textsf{NP} \\
		Errate Variablenbelegung und verifiziere sie.
	\item \textsf{SMERF} ist \textsf{NP}-vollständig \\
		Dies wird gezeigt, indem wir \textsf{MERF} auf \textsf{SMERF} reduzieren. Hierzu müssen lediglich Terme der Form $Y_i \neq a, Y_i = Y_j$ sowie $Y_i \neq Y_j$ überführt werden in Formeln, die nur aus Termen der Form $Y_i = a$ bestehen. \\
		$Y_i \neq a$ wird ersetzt durch:
		$$\begin{cases}false & \mbox{falls } B_i = \{a\} \\ \bigvee_{b \in B_i \setminus \{a\}} (Y_i = b) & \mbox{sonst}\end{cases}$$
		$Y_i = Y_j$ wird ersetzt durch:
		$$\begin{cases}false & \mbox{falls } B_i \cap B_j = \emptyset \\ \bigvee_{a \in B_i \cap B_j} ((Y_i=a) \AND (Y_j=a)) & \mbox{sonst}\end{cases}$$
		$Y_i \neq Y_j$ wird ersetzt durch: $\bigvee ((Y_i=a) \AND (Y_j=b))$ für alle $a \in B_i, b \in B_j$ mit $a \neq b$. Es ist allerdings anzumerken, dass die resultierenden Formeln sehr lang werden können, aber alle gestellten Bedingungen erfüllen.
\end{enumerate}
\textbf{Alternative:} In der Vorlesung haben wir \textsf{P-UNIV} auf \textsf{MERF} reduziert. Dabei haben wir eine Formel konstruiert, die nur Terme der Formen $Y_i = a$ und $Y_i = Y_j$ beinhaltet. Es genügt also, alle Terme der Form $Y_i = Y_j$ wie oben durch Teilformeln zu ersetzen, in denen nur Terme der Form $Y_i = a$ vorkommen. Dies reduziert \textsf{P-UNIV} auf \textsf{SMERF}.

\newpage
\section*{Aufgabe 2}
Gegeben eine Instanz des \textsf{GP}-Problems als $m \times n$-Matrix $M$ und als Vektor $E$ der Länge $n$ sowie eine (angebliche) Lösung des \textsf{GP}-Problems, die als Vektor $L$ der Länge $n$ vorliegt. Für die Lösung muss gelten: $M \cdot L \geq E$, wobei \glqq $\geq$\grqq\ komponentenweise zu verstehen ist. Im naiven Fall erfordert dies pro Ungleichung $n$ Multiplikationen, $n-1$ Additionen sowie einen Vergleich. Nimmt man alle diese Operationen als elementar ($\OnotO(1)$) an, kann man die Lösung in $\OnotO(m \cdot (n+(n-1)+1)) = \OnotO(m \cdot n)$ lösen. Ansonsten erhöht sich der Exponent entsprechend, da aber keine der Operationen exponentiell wird, bleibt die Klasse auf jeden Fall polynomiell. \\[0.5cm]
Es bleibt zu zeigen, dass \textsf{GP} \textsf{NP}-schwer ist. \\
Dazu reduzieren wir von \textsf{3-SAT}: Seien $C=\{C_1, \ldots, C_m\}$ Klauseln bestehend aus jeweils 3 Literalen, basierend auf der Variablenmenge $\{y_1, \ldots, y_n\}$. Zu $C=\{C_1, \ldots, C_m\}$ konstruieren wir in Polynomialzeit eine ganzzahlige Matrix $M$ und einen ganzzahligen Vektor $b$, sodass alle Klauseln $C_1, \ldots C_m$ genau dann gleichzeitig erfüllt sind, wenn es einen ganzzahligen Vektor $x$ mit $Mx \geq b$ gibt. Die Matrix $M$ hat $2n$ Spalten, indiziert mit $y_1,\overline{y_1},\ldots,y_n,\overline{y_n}$. Wir fassen die Ungleichungen $Mx \geq b$ als Ungleichungen in den Literalen auf. Für $i=1, \ldots, n$ haben wir die folgenden Ungleichungen:
\begin{align*}
y_i &\geq 0 \\
\overline{y_i} &\geq 0 \\
y_i + \overline{y_i} &\geq 1 \quad (*) \\
-y_i - \overline{y_i} &\geq -1
\end{align*}
Auf Grund der Ganzzahligkeitsforderung sind diese Ungleichungen genau dann lösbar, wenn $y_i$ und $\overline{y_i}$ nur die Werte 0 und 1 haben, aber nicht beide den gleichen Wert. Dies gilt $\forall i \in \{1, \ldots, n\}$. Für jede Klausel $C_j = z_{j,1} \OR z_{j,2} \OR z_{j,3}, \: j \in \{1, \ldots, m\}$, haben wir dann noch die Ungleichungen
$$z_{j,1} + z_{j,2} + z_{j,3} \geq 1 \quad (**)$$
Die Lösbarkeit von $(**)$ drückt aus, dass mindestens eines der Literale $z_{j,i}, i \in \{1,2,3\}$ in jeder Klausel $C_j$ einen positiven Wert und zusammen mit $(*)$ den Wert 1 haben soll. Die Koeffizienten der linken Seite der Ungleichungen liefern dann die Einträge der Matrix $M$. Die Matrix $M$ hat also Einträge aus der Menge $\{-1,0,1\}$ und hat die Dimension $(m + 4n) \times 2n$. Die Definition des ganzzahligen Vektors $b$ ist auf Grund der rechten Seiten der obigen Ungleichungen offensichtlich. Die Eingabegröße $C = \{C_1, \ldots, C_m\}$ ist $3m$. Wegen $3m \geq n$ haben die Matrix $M$ und der Vektor $b$ zusammen Größe $\OnotO(m^2)$. Die Transformation ist also in Polynomialzeit möglich. \\
Wir müssen noch zeigen, dass $C_1, \ldots, C_m$ genau dann gleichzeitig erfüllbar sind, wenn es einen ganzzahligen Vektor $x$ gibt, der $Mx \geq b$ komponentenweise erfüllt. \\[0.3cm]
\glqq $\Rightarrow$\grqq : Sind die Klauseln $C_1, \ldots, C_m$ gleichzeitig erfüllbar, so gibt es eine Belegung der Variablen mit den Booleschen Werten 0 oder 1, die $C_1, \ldots, C_m$ gleichzeitig erfüllen. Dann sind alle Ungleichungen der Form $(*)$ oder $(**)$ erfüllt. Die Ungleichungen $(**)$ sind erfüllt, da in jeder Klausel mindestens ein Literal den Wert 1 bekommt und alle anderen Werte nicht negativ sind. \\[0.3cm]
\glqq $\Leftarrow$\grqq : Sind alle Ungleichungen $(*)$ und $(**)$ erfüllt, so erhalten wir mit $(*)$ Lösungen $y_i, \overline{y_i} \in \{0,1\}$ mit $y_i + \overline{y_i} = 1$. Die Ungleichungen $(**)$ sind erfüllt, also hat in jeder Klausel mindestens ein Literal den Booleschen Wert 1. Eine Lösung des Ungleichungssystems, gegeben durch $(*)$ und $(**)$, liefert somit eine Belegung der Variablen $y_1, \ldots, y_n$, sodass alle Klauseln gleichzeitig erfüllt sind.

\newpage
\section*{Aufgabe 3}
\begin{itemize}
	\item \textsf{HaPf} $\preccurlyeq_P$ \textsf{HaKr} \\
		Führe folgende Polynomzeittransformation durch:
		\begin{itemize}
			\item Füge einen neuen Knoten ein (1 Schritt)
			\item Füge von jedem alten Knoten eine Kante zu dem neuen ein ($n$ Schritte)
			\item Füge von dem neuen Knoten eine Kante zu jedem alten ein ($n$ Schritte)
		\end{itemize}
		Die Transformation ist also in polynomieller Zeit ($2n+1$) durchführbar und es gilt: Hatte der ursprüngliche Graph einen Hamiltonschen Pfad, so hat der neue einen Hamiltonschen Kreis (gerade über den neuen Knoten). Hat der neue Graph einen Hamiltonkreis, so hatte der alte einen Hamiltonpfad (der Kreis ohne den neuen Knoten).
	\item \textsf{HaKr} $\preccurlyeq_P$ \textsf{HaPf} \\
		Führe folgende Polynomzeittransformation durch:
		\begin{itemize}
			\item Wähle einen Knoten $K$ im Graph (1 Schritt)
			\item Füge zwei neue Knoten $K_1$ und $K_2$ ein (2 Schritte)
			\item Füge für jede Kante, die in $K$ hineingeht, eine entsprechende Kante in $K_1$ ein ($\leq n$ Schritte)
			\item Füge für jede Kante, die aus $K$ herausgeht, eine entsprechende Kanten aus $K_2$ ein ($\leq n$ Schritte)
			\item Lösche $K$ mit allen zugehörigen Kanten ($\leq 2n +1$ Schritte)
		\end{itemize}
		Die Transformation ist also in polynomieller Zeit ($\leq 4n+4$) durchführbar und es gilt: Hatte der ursprüngliche Graph einen Hamiltonschen Kreis, so hat der neue einen Hamiltonschen Pfad (der Kreis wurde an $K$ aufgespalten). Hat der neue Graph einen Hamiltonpfad, so hatte der alte einen Hamiltonkreis (Pfad an $K_1$ und $K_2$ zusammengefügt).
\end{itemize}


\end{document}