Diskussion:Partitionsproblem

Fehler Bearbeiten

Letzter Kommentar: vor 15 Jahren2 Kommentare2 Personen sind an der Diskussion beteiligt

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

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

Laufzeit Bearbeiten

Letzter Kommentar: vor 11 Jahren4 Kommentare4 Personen sind an der Diskussion beteiligt

"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

Abschnitt hinzufügen