\documentclass{bschlangaul-aufgabe}
\bLadePakete{komplexitaetstheorie}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 3},
  Thematik = {NAE3SAT},
  Referenz = 66115-2017-H.T1-A3,
  RelativerPfad = Examen/66115/2017/09/Thema-1/Aufgabe-3.tex,
  ZitatSchluessel = examen:66115:2017:09,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Komplexitätstheorie},
  EinzelpruefungsNr = 66115,
  Jahr = 2017,
  Monat = 09,
  ThemaNr = 1,
  AufgabeNr = 3,
}

% Check-Up
% i o theo ab 4
% i e 66115:2016:03 2 3
% i e 66115:2017:09 1 3

Betrachten\index{Komplexitätstheorie} \footcite{examen:66115:2017:09}
Sie die folgenden Probleme:
\footcite[StEx F2016 T2 A3, StEx H2017 T1 A3 (Check-Up), Aufgabe 15]{theo:ab:4}

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

% https://www.informatik.hu-berlin.de/de/forschung/gebiete/algorithmenII/Lehre/ws09/theo2/skript/thi2-folien-np.pdf

\begin{bExkurs}[NAE3SAT]
Like 3-satisfiability, an instance of the problem consists of a
collection of Boolean variables and a collection of clauses, each of
which combines three variables or negations of variables. However,
unlike 3-satisfiability, which requires each clause to have at least one
true Boolean value, NAE3SAT requires that the three values in each
clause are not all equal to each other (in other words, at least one is
true, and at least one is false)
\bFussnoteUrl{https://en.wikipedia.org/wiki/Not-all-equal_3-satisfiability}
\end{bExkurs}

%%
%
%%

\bPseudoUeberschrift{3SAT}

\begin{description}
\item[Gegeben:]

Eine aussagenlogische Formel $\varphi$ in konjunktiver Normalform (drei
Literale pro Klausel).

\item[Frage:]

Ist $\varphi$ erfüllbar?
\end{description}

%%
%
%%

\bPseudoUeberschrift{NAE-3SAT}

\begin{description}
\item[Gegeben:]

Eine aussagenlogische Formel $\varphi$ in konjunktiver Normalform
(drei Literale pro Klausel).

\item[Frage:]

Gibt es eine Belegung, die in jeder Klausel mindestens ein Literal
\emph{wahr} und mindestens ein Literal \emph{falsch} macht?

\end{description}

\noindent
Wir erlauben, dass \texttt{NAE-3SAT}-Formeln Literale der Form
$\text{false}$ haben, die immer \emph{falsch} sind. So ist

\begin{displaymath}
(x_1 \lor \text{false} \lor \text{false})
\land
(\neg x_1 \lor x_1 \lor x_1)
\end{displaymath}

in \texttt{NAE-3SAT} (setze $x_1$ wahr).
\begin{enumerate}

%%
% a)
%%

\item Zeigen Sie, dass sich \texttt{3SAT} in polynomieller Zeit auf
\texttt{NAE-3SAT} reduzieren lässt.

\begin{bAntwort}
\end{bAntwort}

%%
% b)
%%

\item Was können Sie aus a) folgern, wenn Sie wissen, dass \texttt{3SAT}
NP-vollständig ist?

\begin{bAntwort}
\end{bAntwort}

%%
% c)
%%

\item Was können Sie aus a) folgern, wenn Sie wissen, dass
\texttt{NAE-3SAT} NF-vollständig ist?

\begin{bAntwort}
\end{bAntwort}

\end{enumerate}
\end{document}