\documentclass{bschlangaul-aufgabe}
\bLadePakete{komplexitaetstheorie}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {3SAT - BÜ},
  Referenz = 66115-2018-H.T2-A4,
  RelativerPfad = Examen/66115/2018/09/Thema-2/Aufgabe-4.tex,
  ZitatSchluessel = examen:66116:2018:09,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Polynomialzeitreduktion},
  EinzelpruefungsNr = 66115,
  Jahr = 2018,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 4,
}

Wir betrachten ungerichtete Graphen G = (V, E), wo E eine Teilmenge E.
hat, die wir exklusive Kanten nennen. Eine beschränkte Überdeckung von G
ist eine Teilmenge U von V, so dass\index{Polynomialzeitreduktion}
\footcite{examen:66116:2018:09}

\begin{enumerate}
\item jeder Knoten einen Nachbarknoten in U hat oder selbst in U liegt
(für jeden Knoten u e V U gibt es einen Knoten v € U mit (u,v) € E) und

\item für jede exklusive Kante (u,v) € E. genau einer der Knoten u, v in
U liegt.

\end{enumerate}
Betrachten Sie nun die folgenden Entscheidungsprobleme:

\bProblemBeschreibung
{3SAT}
{Aussagenlogische Formel p in 3KNF}
{Hat o eine erfüllende Belegung?}

\bProblemBeschreibung
{BÜ}
{Graph G = (V, E), exklusive Kantenmenge E. CE
undkeN}
{Hat G eine beschränkte Überdeckung U mit |U| < k?}

Beweisen Sie, dass BÜ NP-vollständig ist. Sie dürfen dabei annehmen,
dass 3SAT NP-vollständig ist.

\end{document}