Diskussion:Partitionsproblem

Letzter Kommentar: vor 11 Jahren von Saqdefaq in Abschnitt Laufzeit

Fehler

Bearbeiten

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  . Dann ist die beste Aufteilung   und   mit der Differenz 2. --AlfonsGeser 11:35, 14. Jun. 2008 (CEST)Beantworten

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

Laufzeit

Bearbeiten

"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)Beantworten

Da hat wohl wer "worst-case" nicht verstanden... (nicht signierter Beitrag von 188.104.0.131 (Diskussion) 20:24, 4. Feb. 2011 (CET)) Beantworten
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)Beantworten

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)Beantworten