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

in crypto •  last year

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: - images and valuable information - easily download and install the BOINC software

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE STEEM!
Sort Order:  

This post was upvoted by Steemgridcoin with the aim of promoting discussions surrounding Gridcoin and science.

This service is free. You can learn more on how to help here.

Have a nice day. :)

Congratulations @mdosev! You have completed some achievement on Steemit and have been rewarded with new badge(s) :

Award for the number of comments

Click on any badge to view your own Board of Honor on SteemitBoard.

To support your work, I also upvoted your post!
For more information about SteemitBoard, click here

If you no longer want to receive notifications, reply to this comment with the word STOP

Upvote this notification to help all Steemit users. Learn why here!