The Citizen Science Grid projects #2 - SubsetSum@Home. BOINC volunteer computing.

The Citizen Science Grid is a project, which is initiated by Travis Desell, an Assistant Professor in the Computer Science Department, University of North Dakota. In a series of posts I will represent the project's details or its sub-projects particularly.

The Citizen Science Grid "hosts" 4 different projects

• DNA@home
• SubsetSum@Home
• Climate Tweets
• Wildlife@Home

So now let's see what exactly the SubsetSum@Home sub-project is dealing with.

---

The Subset Sum task is well known in the mathematics and it is described as follows:

1. A set of positive integers S is given and a target sum t is also available.
2. Is there a subset of S whose sum is t?

This is one of the well-known and so-called "hard" problems in computing. In fact this problem is very easy, and the mathematical algorithm to solve it is not complicated too. What makes the problem hard is the time needed to run this process – the exact algorithms, which are well known, have running time that is proportional to a function of the number of elements in the set and this function is exponential, which exactly makes the project so hard.

So what are the goals of this sub-project?

Over the time, a large number of combinatorial problems, called called NP-complete problems, have been shown to be on the same level of hardness as Subset Sum. Anyway, it is up to how you measure the size of the mathematical problem and for instance, there is some strict evidence that Subset Sum is actually not hard problem at all and is easier that most of the others in its class. The main aim of this sub-project is to strengthen the evidence that Subset Sum is an easier hard problem, no matter how strange sounds this!

In the beginning we have a number of "n" positive whole numbers(named S) which have a maximum number limit (named m). The ratio between n and m (n/m) is defined and this literally is the density of the set. Then we denote the sum of all elements in the set (∑S). If we take a look at the different sums built up by subsets of S, we should observe that almost no one is missing if the number of subsets is dense enough. It appears that the threshold of the density, beyond which there are no sums between m and half the sum of S, can be found and it is exact. The ongoing experiments have led to the hypothesis, claiming that
"A set of positive integers with maximum element "m" and size "n" > floor("m"/2)+1 has a subset with sum is "t" for every "t" in the range "m" <" t" < ∑S −" m"."

---

And where can we help?

The hypothesis above is not still proven. If someone wants to be really helpful, he or she is calmly requested to send the project team a proof (or just show them where and in which research literature can this be found), and the project will be completed in no time. Otherwise, one will be slightly less helpful but! have more fun, if he or she volunteers some computation power and resources to see how far can the team extend the empirical evidence. One will also be helping the team to find better ways to apply distributed computer resources to combinatorial problems.

That's the opportunity for you to have some fun with Mathematics and Gridcoin, and well... maybe be rewarded for your willing to help the science. Science, Medicine, Mathematics, Byology... these fields all make Gridcoin great. Don't hesitate to share some of your free computer resources in the name of science and technological progress.
See you with the next project update later this week. Bye!

---

Sources:
https://www.gridcoin.us/
https://csgrid.org/csg/ - images and valuable information
https://boinc.berkeley.edu/ - easily download and install the BOINC software