Aktionen

SubsetSum@Home

Aus SETI.Germany Wiki

SubsetSum@Home
SubsetSum@Home
Ziel:Vereinfache das Untermengensummen-Problem
Kategorie:Mathematik
Hauptprojekt:Citizen Science Grid
Homepage:http://csgrid.org/csg/subset_sum/
Betreiber:Computer Science Department of the University of North Dakota Vereinigte Staaten von Amerika
Status:alpha
Projektadressen
Serverstatus:SubsetSum@Home
Forum:SubsetSum@Home Forum
SETI.Germany
Team-Statistik:SubsetSum@Home
Teambeitritt:SETI.Germany beitreten
Teamwerbung:Für SubsetSum@Home werben
Twitter Facebook meinVZ/studiVZ
Forenthread:SETI.Germany Forum
Workunit
Frist:4 Tage
Laufzeit:
  • ca. 2:30h, 2:45h, 5:20h
    (Odroid XU4, S4 (2 Kerne), S2 (1 Kern))
Erster Download:nur SubsetSum_0.11_arm-android-linux-gnu 295 MB
Download:90 Bytes
Arbeitsspeicher:Max. RAM: 47.7 Virtueller RAM: 1.2
Betriebssysteme:Android Linux 32 Bit Linux 64 Bit Windows 32 Bit Windows 64 Bit
Bildschirmschoner:Nicht vorhanden
Checkpoints:Vorhanden
es gibt gelegentlich Aufgaben für Android (running on ARM v0.11)

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.

Badges

Bronze
10.000
Credits
Silber
100.000
Credits
Gold
500.000
Credits
Amethyst
1 Mio
Credits
Ruby
2 Mio
Credits
'Sapphire
5 Mio
Credits
Turquoise
10 Mio
Credits
Jade
20 Mio
Credits
Emerald
50 Mio
Credits
SubSetSum@Home
Badges
Badge SSS bronze.png Badge SSS silver.png Badge SSS gold.png Badge SSS amethyst.png Badge SSS ruby.png Badge SSS sapphire.png Badge SSS turquoise.png Badge SSS jade.png Badge SSS emerald.png

Weblinks