\documentclass{bschlangaul-aufgabe}
\bLadePakete{komplexitaetstheorie}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {IF ISAT SAT},
  Referenz = 66115-2020-H.T1-TA1-A5,
  RelativerPfad = Examen/66115/2020/09/Thema-1/Teilaufgabe-1/Aufgabe-5.tex,
  ZitatSchluessel = examen:66115:2020:09,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Komplexitätstheorie, Polynomialzeitreduktion},
  EinzelpruefungsNr = 66115,
  Jahr = 2020,
  Monat = 09,
  ThemaNr = 1,
  TeilaufgabeNr = 1,
  AufgabeNr = 5,
}

Sei \bProblemName{If} die Menge aller aussagenlogischen Formeln, die
ausschließlich mit den Konstanten $0$ und $1$, logischen Variablen $x_i$
mit $i \in N$ und der Implikation $\Rightarrow$ als Operationszeichen
aufgebaut sind, wobei natürlich Klammern zugelassen sind. Beachten Sie,
dass $x_i \Rightarrow x_j$ die gleiche Wahrheitstabelle wie $\neg x_i
\lor x_j$ hat.\index{Komplexitätstheorie}
\footcite{examen:66115:2020:09}

Wir betrachten das Problem \bProblemName{Isat}. Eine Formel $F \in
\bProblemName{If}$ ist genau dann in \bProblemName{Isat} enthalten,
wenn sie erfüllbar ist, das heißt, falls es eine Belegung der Variablen
mit Konstanten $0$ oder $1$ gibt, sodass $F'$ den Wert $1$ annimmt.

Zeigen Sie: \bProblemName{Isat} ist NP-vollständig. Sie dürfen
benutzen, dass das \bProblemName{Sat}-Problem NP-vollständig ist.
\index{Polynomialzeitreduktion}

\begin{bAntwort}
\bMetaNochKeineLoesung
\end{bAntwort}

\end{document}