Algorithmus transformieren ...
-
otze schrieb:
Michael E. schrieb:
Ist das Subset-Sum? Immerhin hat man nur sehr wenige verschiedene Münztypen.
naja, ich halte es für eine Instanz von Subset-Sum die polynomiell lösbar ist. Das war ja eigentlich mein Argument: es gibt zu jedem NP-Problem Untermengen für die eine Polynomialzeit-Algorithmus existiert.
Eine einzelne Instanz ist trivialerweise in Polynomialzeit lösbar, weil "Polynomialzeit" sich auf irgendeine Größe bezieht, die wachsen können muss. Aber aus deinem zweiten Satz schließe ich, dass du eigentlich eine Menge von Instanzen meinst, die alle in Polynomialzeit lösbar sind, also anders gesagt eine eingeschränkte Variante des Subset-Sum-Problems.
otze schrieb:
Dadurch wird es nicht weniger "Subset-Sum" es ist halt ein Spezialfall.
Doch, es wird dadurch weniger Subset-Sum. Im üblichen Sprachgebrauch der Literatur meint man mit 3SAT, subset sum, TSP, etc. nur die NP-vollständigen Versionen der entsprechenden Probleme. Es wär sonst etwas zu verwirrend, wenn man das immer dazuschreiben müsste.