SubsetSum@Home: Unterschied zwischen den Versionen
Zur Navigation springen
Zur Suche springen
(description) |
KKeine Bearbeitungszusammenfassung |
||
| Zeile 7: | Zeile 7: | ||
Ziel des Projektes ist es, die Anzeichen zu bestätigen, dass das Untermengensummen-Problem einfacher lösbar ist als andere NP-vollständige kombinatorische Probleme. | Ziel des Projektes ist es, die Anzeichen zu bestätigen, dass das Untermengensummen-Problem einfacher lösbar ist als andere NP-vollständige kombinatorische Probleme. | ||
'''Hypothese''' | '''Hypothese'''<br> | ||
Sei S eine Menge natürlicher Zahlen der Mächtigkeit n mit dem größten Element m. Als Dichte der Menge wird n/m definiert, die Summe aller Elemente der Menge sei ΣS. | Sei S eine Menge natürlicher Zahlen der Mächtigkeit n mit dem größten Element m. Als Dichte der Menge wird n/m definiert, die Summe aller Elemente der Menge sei ΣS. | ||
Version vom 9. Mai 2013, 07:44 Uhr
 |
[[::SubsetSum@Home|Deutsch]] • [[::SubsetSum@Home/en|English]] |
| Ziel des Projektes ist es, die Anzeichen zu bestätigen, dass das Untermengensummen-Problem einfacher lösbar ist als andere NP-vollständige kombinatorische Probleme.
Hypothese Betrachtet man die Liste der Elementsummen von Untermengen von S, stellt man fest, dass man bei hinreichender Dichte von S fast jede Summe erzeugen kann. Es scheint eine scharfe Grenzdichte zu geben, ab der jede Summe zwischen m und ΣS/2 dargestellt werden kann. Das Projekt versucht, folgende Behauptung zu stützen: Jede Menge natürlicher Zahlen S mit größtem Element m und Mächtigkeit n > floor(m/2)+1 hat eine Untermenge mit der Elementsumme t für jedes t mit m < t < ΣS-m. |
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
[[::SubsetSum@Home|Deutsch]] • [[::SubsetSum@Home/en|English]] |