\documentclass{bschlangaul-aufgabe}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 5},
  Thematik = {BEHAELTER GERADEBEHAELTER},
  Referenz = 66115-2019-F.T1-A5,
  RelativerPfad = Examen/66115/2019/03/Thema-1/Aufgabe-5.tex,
  ZitatSchluessel = examen:66115:2019:03,
  BearbeitungsStand = nur Angabe,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Komplexitätstheorie, Polynomialzeitreduktion},
  EinzelpruefungsNr = 66115,
  Jahr = 2019,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 5,
}

Wir betrachten das Behälterproblem BEHAELTER. Gegeben ist eine Menge von
k € N Behältern, die jeweils ein Fassungsvermögen der Größe b € N haben.
Gegeben sind weiterhin n Objekte mit jeweiligen Größen aı,...,@„.
Gesucht ist eine Zuordnung der n Objekte auf die k Behälter, sodass
keiner der Behälter überläuft.\index{Komplexitätstheorie}
\footcite{examen:66115:2019:03}

Formal sind Instanzen des Behalterproblems BEHAELTER durch Tupel (k,,
a1,...@n) gegeben, die wie folgt zu interpretieren sind:

\begin{itemize}
\item k EN steht für eine Anzahl von Behältern.

\item Jeder Behälter hat ein Fassungsvermögen von bEN.

\item  Die a, stehen für die jeweiligen Größen von n Objekten.
\end{itemize}

Zuordnungen von Objekten zu Behältern geben wir durch eine Funktion v
an, wobei v(j) = i wenn das j-te Objekt (mit Größe a,) dem i-ten
Behälter zugeordnet wird.

(k,b,aı,...Q,) ist eine JA-Instanz von BEHAELTER, wenn es eine Zuordnung
v von Objekten auf Behälter (v : [1;n] — [1; k]) gibt, die sicherstellt,
dass kein Behälter überläuft:

(k,b,a1,...4n) € BEHABLTER <=> (3v: [1;n] > [1;k]. Vik. S> a; <0)
i=v(3)

Wir betrachten auch das modifizierte Problem GERADEBEHAELTER. Instanzen
von GERADEBEHAELTER tragen die zusätzliche Einschränkung, dass alle a;
gerade (durch zwei teilbar) sein müssen.

\begin{enumerate}

%%
% (a)
%%

\item Warum ist sowohl BEHAELTER € NP als auch GERADEBEHAELTER € NP?

%%
% (b)
%%

\item Beweisen Sie, dass das Problem BEHAELTER auf das Problem
GERADEBEHAELTER in polynomieller Zeit reduzierbar ist.
\index{Polynomialzeitreduktion}

%%
% c)
%%

\item BEHAELTER ist NP-vollständig. Begründen Sie, was obige Reduktion
für die Komplexität von GERADEBEHAELTER bedeutet. BEHAELTER ist
NP-vollständig. Begründen Sie, was obige Reduktion für die Komplexität
von GERADEBEHAELTER bedeutet.

\end{enumerate}
\end{document}