SubsetSum@Home

Aus BC-Wiki
Wechseln zu: Navigation, Suche
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.


Subsetlist.png

Erde.png SubsetSum@Home
Beginn 2012
Ende Oktober 2016
Status beendet
Admin Travis Desell
Institut Universität Nord Dakota
Land USA
Bereich Mathematik
Info.png Anwendungen
Win.png Win SubsetSum@Home Sum Calculator 0.16
Linux2.png Linux SubsetSum@Home Sum Calculator 0.16
Macos.gif Mac SubsetSum@Home Sum Calculator 0.16
Amd64.jpg 64bit SubsetSum@Home Sum Calculator 0.16 [linux/win/mac]
Ps3.png PS3
Ati.jpg ATI
Cuda.jpg CUDA
Intel.jpg Intel
Android.png Android Yes.gif
Raspberri Pi.png RPi No.gif
Nci.jpg NCI No.gif
Specs.png Systemspezifikationen
VRAM SP No.gif DP No.gif
RAM 1,3MB
Laufzeit 30min
HDD 0,7MB
Traffic dl/ul kb / kb
Deadline 4 Tage
Checkpoints Yes.gif