The R(m, n) instance of the party problem asks how many people must attend a party to guarantee that at the party, there is a group of m people who all know each other or a group of n people who are all complete strangers. GPUs have been shown to significantly decrease the running time of some mathematical and scientific applications that have embarrassingly parallel portions. A brute force algorithm to solve the R(5, 5) instance of the party problem can be parallelized to run on a number of processing cores many orders of magnitude greater than the number of cores in the fastest supercomputer today. Therefore, we believed that this currently unsolved problem is so computationally intensive that GPUs could significantly reduce the time needed to solve it. In this work, we compare the running time of a naive algorithm to help make progress solving the R(5, 5) instance of the party problem on a CPU and on five different GPUs ranging from low-end consumer GPUs to a high-end GPU. Using just the GPUs computational capabilities, we observed speedups ranging from 1.9 to over 21 in comparison to our quad-core CPU system.


  • Computer Science > General
  • Mathematics > General

Education Levels:

  • Grade 1
  • Grade 2
  • Grade 3
  • Grade 4
  • Grade 5
  • Grade 6
  • Grade 7
  • Grade 8
  • Grade 9
  • Grade 10
  • Grade 11
  • Grade 12


Informal Education,oai:nsdl.org:2200/20121226195601510T,NSDL,Graduate/Professional,NSDL_SetSpec_ncs-NSDL-COLLECTION-000-003-112-055,Higher Education,Computer Science,Vocational/Professional Development Education,Mathematics,General Public,Computing and Information



Access Privileges:

Public - Available to anyone

License Deed:

Creative Commons Attribution Non-Commercial Share Alike


This resource has not yet been aligned.
Curriki Rating
'NR' - This resource has not been rated
'NR' - This resource has not been rated

This resource has not yet been reviewed.

Not Rated Yet.

Non-profit Tax ID # 203478467