Hallo,
in den Lösungshinweisen zu Müllabfuhr wurde die NP-Schwere des Müllabfuhrproblems durch eine Reduktion von Subset Sum bewiesen. Subset Sum ist aber in polynomieller Zeit lösbar, wenn der Wert der Zahlen durch ein Polynom in n begrenzt ist. Das heißt aber doch, dass der Beweis nur zeigt, dass das Müllabfuhrproblem nicht in polynomieller Zeit lösbar ist, wenn die Kantengewichte nicht durch ein Polynom in n begrenzt sind, oder?
Viele Grüße, Finn
Hey Finn,
meines Wissens nach ist das "Subset-Sum"-Problem in pseudopolynomieller Zeit lösbar. D.h. es ist schwach NP-schwer.
D.h. hier die Laufzeit ist polynominell in der Zahlen N (Anzahl der Zahlen) und T (gesuchte Zahl). Beispielsweise kann durch die Dynamische Programmierung eine Laufzeit von O(N*T) erreicht werden. Wie du erklärt hast, ist diese Laufzeit selbstverständlich polynominell, wenn N und T durch Polynome in N begrenzt werden.
Eine andere Möglichkeit die Laufzeit zu interpretieren, ist die Codierung von N und den Zahlen der Menge S. Im folgenden sei die Eingabelänge des Problems m. Also die Anzahl an Symbole, die gebraucht werden um die Zahl T und die Zahlen der Menge S zu codieren.
Codiert man die Zahlen nun unär (d.h. nur mit Einsen), so ist N*T tatsächlich ein Polynom in m, denn um beispielsweise die Zahl N zu codieren braucht man tatsächlich N Einsen.
Codiert man die Zahlen allerdings in binär (oder mit einer höheren Basis), so ist N*T exponentiell in m. Denn um beispielsweise N zu codieren braucht man nur log_2(N) Symbole.
Insgesamt stimm ich die also zu, was deine Behauptung angeht. Durch die Reduktion wurde gezeigt, dass das Müllabfuhrproblem mindestens so schwer ist, wie das Subset-Sum-Problem. Ich denke allerdings, dass das Problem tatsächlich auch stark NP-schwer ist, d.h. dass es nicht in pseudopolynomieller Zeit gelöst werden kann.
LG,
Florian