Komplexitätstheorie Hausaufgaben 5

Hausaufgabe 5.1

Löse das Rucksack Problem von http://www.princeton.edu/~civ105/LAB2/index.html (Frage 2).

Hausaufgabe 5.2

Zeige, daß das Problem PARTITION NP-vollständig ist:

Gegeben: Natürliche Zahlen a_1, a_2, ..., a_k.
Gefragt: Gibt es eine Teilmenge der Indizes dieser Zahlen, so daß die Summe der entsprechenden Zahlen genau das gleiche ergibt wie die Summe der restlichen Zahlen?

Beispiel:

1, 2, 3 kann in 1+2 = 3 partitioniert werden.

1, 2, 4 kann nicht in zwei Teile partitioniert werden.

Hinweis: SUBSET-SUM.

Hausaufgabe 5.3

Zeige, daß das Problem BIN PACKING NP-vollständig ist:

Gegeben: Eine Behältergröße b, die Anzahl der Behälter k, und n Objekte mit Größen a_1, a_2, ..., a_n <= b (alles natürliche Zahlen).
Gefragt: Können die Objekte so in die Behälter verteilt werden, daß kein Behälter überläuft?

Beispiel:

Objekte mit Größen 2, 3, 3, 4, 5 können in k=3 Behälter der Größe b=6 verteilt werden.

Bei Objekten mit Größen 2, 3, 4, 4, 5 geht das nicht.

Hausaufgabe 5.4

Es ist ein offenes Problem, ob das Entscheidungsproblem "Ist eine natürliche Zahl n zusammengesetzt (= keine Primzahl)?" in polynomieller Zeit in der Eingabegröße berechnet werden kann. Warum genügt der folgende O(n)-Zeit Algorithmus nicht, um zu zeigen, daß das Problem in P liegt?

PrimzahlTest(n)
   for i:=2 to n-1 do
      if (n mod i) = 0 then
         return "Nicht Prim"
   return "Prim"