Diskussion:Partitionsproblem

Fehler

Was bedeutet es, wenn es heisst die minimale Differenz sei 0 oder 1? Das ergibt keinen Sinn.

89.245.101.13 meint hier wohl: "Das kann nicht stimmen." Er hat recht. Gegenbeispiel: Gegeben sei die Menge $\{3,5,10\}$. Dann ist die beste Aufteilung $\{3,5\}$ und $\{10\}$ mit der Differenz 2. --AlfonsGeser 11:35, 14. Jun. 2008 (CEST)

Na, dann löschen Wir dass doch mal.--Leuman 20:05, 15. Nov. 2008 (CET)

Laufzeit

"Das Partitionsproblem gehört zu den 21 klassischen NP-vollständigen Problemen [...] Es hat eine „worst-case-Laufzeit“, die exponentiell mit der Anzahl der Zahlen N wächst". Na, wenn das so ist, dann ist wohl NP≠P und NP=EXP gezeigt... -- 92.196.75.38 09:19, 19. Apr. 2009 (CEST)

Da hat wohl wer "worst-case" nicht verstanden... (nicht signierter Beitrag von 188.104.0.131 (Diskussion) 20:24, 4. Feb. 2011 (CET))

Ja, und zwar Du (188.104.0.131). Im übrigen haben PROBLEME niemals eine „worst-case-Laufzeit“...

Wenn P=NP wäre, dann wäre die worst-case-Laufzeit nicht exponentiell. Genauer gesagt kennen wir schlichtweg momentan keinen Algorithmus mit einer besseren als exponentialer Laufzeit. Bitte sichten und bestätigen. --Saqdefaq (Diskussion) 21:48, 11. Feb. 2013 (CET)

Ich habe nochmal dies und einige weitere Ungereimtheiten ausgebessert. Insbesondere war wohl der ganze Absatz über dynamische Programmierung von irgenwo anders hierher kopiert (Vandalismus?). Hab auf die Schnelle den korrekten Algo eingefügt. Mit statistischer Physik kenne ich mich nicht so gut aus - daher hab ich den Abschnitt so gelassen - erscheint mir aber auch überarbeitungsbedürftig.--Graf Alge 19:12, 27. Apr. 2011 (CEST)