Berechnungskomplexitäten von Varianten des Subset-Sum-Problems

In dieser Arbeit betrachten wir das Problem subsetsum, bei dem aus ei-
ner gegebenen Menge von natürlichen Zahlen eine Teilmenge bestimmt
werden soll, sodass die Elemente dieser Teilmenge in der Summe ei-
ne vorgegebene Zahl ergeben. Die Komplexität von subsetsum ist für
die Informatik interessant, denn aufgrund des generischen Aufbaus
von subsetsum lassen sich viele weitere Probleme darauf zurückfüh-
ren. In dieser Arbeit soll die Komplexität von mehreren Varianten von
subsetsum untersucht werden, denn obwohl fast alle Varianten des Pro-
blems in der üblichen binären Codierung NP-vollständig sind, haben
diese Probleme oft unterschiedliche Komplexitäten, wenn wir unäre
Kodierungen betrachten. In dieser Arbeit werden einige natürliche Va-
rianten dieses Problems diesbezüglich untersucht und entsprechende
Resultate präsentiert.