\documentclass{bschlangaul-aufgabe}
\bLadePakete{komplexitaetstheorie}
\begin{document}
\def\sat{\bProblemName{Sat}}
\def\dreiSat{\bProblemName{3Sat}}

\bAufgabenMetadaten{
  Titel = {SAT-3SAT},
  Thematik = {SAT-3SAT},
  Referenz = THEO.Komplexitaet.SAT-3SAT,
  RelativerPfad = Module/70_THEO/40_Komplexitaet/Aufgabe_SAT-3SAT.tex,
  ZitatSchluessel = theo:ab:4,
  ZitatBeschreibung = {Seite 18, Aufgabe 14},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Polynomialzeitreduktion},
}

\begin{bExkurs}[\sat]
\bProblemSat
\end{bExkurs}

\begin{enumerate}

%%
% (a)
%%

\item Wie zeigt man die aus der NP-Schwere des \dreiSat-Problems die
NP-Schwere des \sat-Problems?\index{Polynomialzeitreduktion}
\footcite[Seite 18, Aufgabe 14]{theo:ab:4}

\begin{bAntwort}
\bPolynomiellReduzierbar{\dreiSat}{\sat}

Jedes \dreiSat-Problem ist auch ein \sat-Problem,
weil $\dreiSat \subset \sat$. Damit braucht es keine Funktion (bzw.
Identitäts-/Einheitsfunktion). Die Funktion ist korrekt, total und in
Polynomialzeit anwendbar. Das \sat-Problem ist ebenfalls NP-schwer.
\end{bAntwort}

%%
% (b)
%%

\item Wie zeigt man die aus der NP-Schwere des \sat-Problems die
NP-Schwere des \dreiSat-Problems?

\begin{bAntwort}
\bPolynomiellReduzierbar{\sat}{\dreiSat}

Man muss eine Funktion finden, die eine allgemeine Aussagenlogik in eine
Aussagenlogik mit 3 Literalen in konjunktiver Normalform umformt.

Durch die boolsche Algebra lässt sich jede logische Aussagenlogik in
eine konjunktive Normalform bringen. Dies ist eine Konjunktion von
Disjunktionstermen. Wir formen einen Disjunktionsterm mithilfe einer
Funktion in ein \dreiSat-Problem um. Diese Funktion kann auf jeden
Disjunktionsterm angewendet werden und damit wird das gesamte
\sat-Problem auf \dreiSat{} reduzieren.

Die Funktion formt Formel aus \sat mithilfe von Hilfsvariablen
%
$h_1 , \dots , h_{n-2}$
%
derart um
%
$(a_1 \lor \dots \lor a_n) \rightarrow
(a_1 \lor a_2 \lor h_1) \land
(\neg h_1 \lor a_3 \lor h_2) \land
(\neg h_2 \lor a_4 \lor h_3) \land
\dots \land
(\neg h_{n-2} \lor a_n )$

\begin{description}
\item[total]

Diese Funktion ist total, denn jede in \sat enthaltene Aussagenlogik
kann so umgewandelt werden.

\item[Korrektheit:]

Die Hilfsvariablen sind wahr, solange bis ein Literal $a_x$
selber true ist. Ab diesem Zeitpunkt sind die Hilfsvariablen dann
falsch.

\begin{description}
\item[JA-Instanzen:]

Der erste und alle mittleren Disjunktionstermen sind wahr, weil aufgrund
der Nicht-Negierung und Negierung immer ein wahres Literal in den
Disjunktionstermen. Somit ist dann auch der Disjunktionsterm wahr. Da es
eine JA-Instanz ist, existiert ein $a_x$ welches wahr ist. Somit sind ab
diesem Zeitpunkt die Hilfvariablen falsch. Der letzte Disjunktionsterm
wird dadurch sicher wahr, weil $\neg h_{n-2}$ somit wahr ist.

\item[NEIN-Instanz:]

Alle $a_x$ sind falsch. Auch hier sind wieder der erste und alle mittleren
Disjunktionsterme wahr (gleiche Begründung wie oben). Der letzte
Disjunktionsterm ist allerdings falsch, weil die Hilfvariablen
durchgehend wahr bleiben und alle $a_x$ falsch sind. Durch die Konjunktion
der Disjunktionsterme ist dann auch die Gesamtaussage falsch.

\end{description}

\item[Polynomialzeit:]

Der Algorithmus, der Formeln aus \sat{} nach \dreiSat{} umformt liegt in
$\mathcal{O}(n)$ und somit in Polynomialzeit.
\end{description}
\end{bAntwort}
\end{enumerate}

\end{document}