http://volunteer.cs.und.edu/subset_sum/index.php
About SubsetSum@Home
The Subset Sum problem is described as follows: given a set of positive integers S and a target sum t, is there a subset of S whose sum is t? It is one of the well-know, so-called “hard†problems in computing. It's actually a very simple problem, and the computer program to solve it is not extremely complicated. What's hard about it is the running time – all known exact algorithms have running time that is proportional to an exponential function of the number of elements in the set (for worst-case instances of the problem).
Over the years, a large number of combinatorial problems have been shown to be in the same class as Subset Sum (called NP-complete problems). But, depending on how you measure the size of the problem instance, there is evidence that Subset Sum is actually an easier problem that most of the others in its class. The goal of this project is to strengthen the evidence that Subset Sum is an easier hard problem.
Suppose we have a set of n positive whole numbers S whose maximum number is m. We will define the ratio n/m to be the density of the set and denote the sum of all elements in the set as ∑S. If you look at the list of sums produced by subsets of S, you notice that very few sums are missing if S is dense enough. In fact, it appears that there is an exact density threshold beyond which no sums between m and half the sum of S will be missing. Our preliminary experiments have led to the following hypothesis: A set of positive integers with maximum element m and size n > floor(m/2)+1 has a subset whose sum is t for every t in the range m < t < ∑S − m.
So here's where you can help. So far, we haven't been able to prove the hypothesis above. If you want to be really helpful, you can send us a proof (or show us where to find one in the research literature), and the project will be done. But if you want to be slightly less helpful and have more fun, you can volunteer your computer as a worker to see how far we can extend the empirical evidence. You will also be helping us figure out better ways to apply distributed computing to combinatorial problems.
You can track the current progress of the project here.
SubsetSum@Home is based at the Computer Science Department of the University of North Dakota.
SubsetSum@Home project details
Jump to
- Guest Access Forum
- General
- ↳ Fun and Games
- ↳ General
- ↳ Newshound RSS feeds
- ↳ Welcome
- ↳ Sneak Peak - Yearly Team Individual Stats Competition
- Competitions and Kudos
- ↳ Badges? We don't need no stinkin' badges!
- ↳ Kudos
- ↳ Milestones
- ↳ Milestones Archives
- ↳ Throw down the Gauntlet
- ↳ Pending Competitions
- ↳ archive
- ↳ TSBT Competitions
- Home Port of Anguillan Pirates
- ↳ Anguillan Pirates
- ↳ Pirates on Tour
- Hardware
- ↳ ASIC & FPGA Enchanced Devices
- ↳ Benchmarking and Hardware
- ↳ Graphics Processing Unit (GPU)
- ↳ Single-board Computers
- Operating Systems & Software
- ↳ Android
- ↳ BOINC Software Applications
- ↳ Linux
- ↳ Mac OS
- ↳ Microsoft Windows
- ↳ BOINC Technical Conventions and Papers
- ↳ FreeBSD
- BOINC Projects
- ↳ Biology / Medical
- ↳ GPUgrid
- ↳ RNA World
- ↳ Rosetta
- ↳ SiDock
- ↳ TN-Grid
- ↳ CERN
- ↳ LHC
- ↳ ATLAS
- ↳ Beauty
- ↳ CSM
- ↳ vLHC
- ↳ Chemistry
- ↳ QuChemPedIA
- ↳ Earth Sciences
- ↳ Climate Prediction
- ↳ Quake Catcher
- ↳ Mathematics / Computing
- ↳ Amicable Numbers
- ↳ Collatz Conjecture
- ↳ Gerasim
- ↳ GPUGRID
- ↳ iTHENA
- ↳ Loda
- ↳ NFS
- ↳ NumberFields
- ↳ ODLK
- ↳ ODLK1
- ↳ PGFNS
- ↳ PrimeGrid
- ↳ RakeSearch
- ↳ SRBase
- ↳ T.Brada
- ↳ ramanujan
- ↳ Van Der Waerden Numbers
- ↳ Wanless
- ↳ YAFU
- ↳ Physics
- ↳ nanoHub
- ↳ RADIOACTIVE
- ↳ Social Sciences
- ↳ MindModeling
- ↳ Space Sciences
- ↳ Asteroids
- ↳ Cosmology
- ↳ Einstein
- ↳ Gaia@home
- ↳ MilkyWay
- ↳ Universe
- ↳ Umbrella projects
- ↳ BOINC@TACC
- ↳ Citizen Science Grid
- ↳ Wildlife@Home
- ↳ DNA@Home
- ↳ SubsetSum@Home
- ↳ Moo! Wrapper
- ↳ yoyo
- ↳ World Community Grid
- ↳ General Posts
- ↳ Africa Rainfall Project
- ↳ Fight AIDS
- ↳ Help Cure Muscular Dystrophy
- ↳ Help Stop TB
- ↳ Mapping Cancer Markers
- ↳ Microbiome Immunity Project
- ↳ OpenPandemics - COVID-19
- ↳ Open Zika
- ↳ Outsmarting Ebola
- ↳ Smash Childhood Cancer
- ↳ Retired Projects
- ↳ Brainstorm
- ↳ Miscellaneous
- ↳ WUProp
- ↳ Permanent Testing
- ↳ Albert
- ↳ BURP
- ↳ RALPH
- ↳ Retired Projects
- ↳ ABC@home
- ↳ ABC Lattices
- ↳ Acoustics
- ↳ AlmereGrid Boinc Grid
- ↳ AlmereGrid TestGrid
- ↳ AndersonAttack@home
- ↳ Beal@Home
- ↳ Bitcoin Utopia
- ↳ CAS
- ↳ Chess960@Home
- ↳ Constellation
- ↳ CONVECTOR
- ↳ Correlizer
- ↳ Climate@Home
- ↳ Climateprediction.net Beta
- ↳ DBN UPPER BOUND
- ↳ DENIS
- ↳ DistrRTgen
- ↳ DHEP
- ↳ DistributedDataMining
- ↳ DrugDiscovery@Home
- ↳ DrugDiscovery
- ↳ Docking@Home
- ↳ Duchamp
- ↳ EDGeS@Home
- ↳ Enigma
- ↳ eOn
- ↳ FiND@Home
- ↳ iGEM@Home
- ↳ Goofyxgrid
- ↳ Gridcoin Finance
- ↳ ibercivis
- ↳ Ideologias@Home
- ↳ Kryptos@Home
- ↳ Lattices @Home
- ↳ Leiden Classical
- ↳ Malaria Control
- ↳ Najmanovich Research Group
- ↳ Nanosurface@home
- ↳ Neurona@Home
- ↳ OProject@Home
- ↳ OPTIMA@HOME
- ↳ Physics
- ↳ Pirates@Home
- ↳ Plagiarism@Home
- ↳ POEM@HOME
- ↳ Primaboinca
- ↳ QMC@Home
- ↳ Rioja Science
- ↳ Renderfarm.fi
- ↳ SAT@home
- ↳ SETI
- ↳ SETI Beta
- ↳ SimOne@home
- ↳ SIMAP Production
- ↳ SLinCA
- ↳ Spatiotemporal Quality of Service (QoS)
- ↳ Stop@home
- ↳ Superlink@Technion
- ↳ SZTAKI
- ↳ The Lattice Project
- ↳ theSkyNet POGS
- ↳ VGTU
- ↳ Virtual Prairie
- ↳ Volpex
- ↳ XANSONS for COD
- ↳ Non-BOINC Projects
- Links and Help Section
- ↳ Links
- ↳ Help
- ↳ Website Problems