\documentclass{bschlangaul-aufgabe}
\bLadePakete{komplexitaetstheorie}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Post‘sches Korrespondenzproblem (PCP) und Modifiziertes Post‘sches Korrespondenzproblem (MPCP)},
  Thematik = {PCP und MPCP},
  Referenz = THEO.Entscheidbarkeit.MPCP,
  RelativerPfad = Module/70_THEO/30_Entscheidbarkeit/Aufgabe_MPCP.tex,
  ZitatSchluessel = hoffmann,
  ZitatBeschreibung = {Seite 326-330},
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Entscheidbarkeit},
}

Post‘sches Korrespondenzproblem\footcite[Seite 326-330]{hoffmann}
\index{Entscheidbarkeit}
\footcite[Seite 46-48]{theo:fs:4}

\bProblemBeschreibung{PCP}
{$(x_1, y_1), \dots, (x_n, y_n)$ mit $x_1, y_1 \in \Sigma +$}
{Gibt es eine Folge $i_1, i_2, \dots, i_k \in \mathbb{N}$ mit der Eigenschaft
$x_{i_1} x_{i_2} \dots x_{i_k} = y_{i_1} y_{i_2} \dots y_{i_k}$}

Modifiziertes Post‘sches Korrespondenzproblem

\bProblemBeschreibung{MPCP}
{$(x_1, y_1), \dots, (x_n, y_n)$ mit $x_1, y_1 \in \Sigma +$}
{Gibt es eine Folge $i_1, i_2, \dots, i_k \in \mathbb{N}$ mit der Eigenschaft
$x_{i_1} x_{i_2} \dots x_{i_k} = y_{i_1} y_{i_2} \dots y_{i_k}$}

\end{document}