\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {NP},
  Referenz = 46115-2016-F.T1-A5,
  RelativerPfad = Examen/46115/2016/03/Thema-1/Aufgabe-5.tex,
  ZitatSchluessel = examen:46115:2016:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Komplexitätstheorie},
  EinzelpruefungsNr = 46115,
  Jahr = 2016,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 5,
}

Beschreiben Sie, was es heißt, dass ein Problem (Sprache) NP-vollständig
ist. Geben Sie ein NP-vollständiges Problem Ihrer Wahl an und erläuteren
Sie, dass (bzw.) warum es in NP liegt.
\index{Komplexitätstheorie}
\footcite{examen:46115:2016:03}
\footcite[Seite 15, Aufgabe 11]{theo:ab:4}

\begin{bAntwort}
NP-vollständig: NP-schwer und in NP

[Beliebiges Problem] liegt in NP, da der entsprechende Algorithmus
dieses Problem nicht-deterministisch in Polynomialzeit löst → Algorithmus rät
nichtdeterministisch Lösung, prüft sie in Polynomialzeit
\end{bAntwort}

\end{document}