SubsetSum@Home

Aus BC-Wiki
Version vom 17. Mai 2018, 12:44 Uhr von DoctorNow (Diskussion | Beiträge) (Code-Korrektur)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen
Dies war früher ein eigenständiges Projekt, ist aber jetzt Teil von Citizen Science Grid.

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
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.

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
Beginn 2012
Ende Oktober 2016
Status beendet
Admin Travis Desell
Institut Universität Nord Dakota
Land USA
Bereich Mathematik
Anwendungen
Win SubsetSum@Home Sum Calculator 0.16
Linux SubsetSum@Home Sum Calculator 0.16
Mac SubsetSum@Home Sum Calculator 0.16
64bit SubsetSum@Home Sum Calculator 0.16 [linux/win/mac]
PS3
ATI
CUDA
Intel
Android
RPi
NCI
Systemspezifikationen
VRAM SP DP
RAM 1,3MB
Laufzeit 30min
HDD 0,7MB
Traffic dl/ul kb / kb
Deadline 4 Tage
Checkpoints