\documentclass{bschlangaul-aufgabe}
\bLadePakete{komplexitaetstheorie}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 7},
  Thematik = {SAT},
  Referenz = 66115-2014-F.T1-A7,
  RelativerPfad = Examen/66115/2014/03/Thema-1/Aufgabe-7.tex,
  ZitatSchluessel = examen:66115:2014:03,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Komplexitätstheorie},
  EinzelpruefungsNr = 66115,
  Jahr = 2014,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 7,
}

\begin{enumerate}

%%
% a)
%%

\item Sei \bProblemName{Sat} das Erfüllbarkeitsproblem, und sei $H_m$,
das Halteproblem bei fester Eingabe $m$ (siehe Aufgabe 5).
\index{Komplexitätstheorie}
\footcite{examen:66115:2014:03}

Zeigen Sie: \bProblemName{Sat} kann in polynomieller Zeit auf $H_m$
reduziert werden. Als Relation:

\bPolynomiellReduzierbar{Sat}{$H_m$}

%%
% b)
%%

\item Angenommen, es wurde gezeigt, dass $P = NP$ ist. Zeigen Sie, dass
dann jede Sprache $L \in P$ über dem Alphabet $\Sigma$ mit $L \neq
\emptyset$ und $L \neq \Sigma^*$ sogar NP-vollständig ist.

\end{enumerate}
\end{document}