A group of N kids what to split up into two teams that are evenly matched. If the skill of each player is measured by an integer, can the kids be split into two groups such that the sum of the skills in each group is the same? This is the number partitioning problem, a classic and surprisingly difficult problem in computer science. In particular, it is NP-complete; it belongs to a category of problems for which no known algorithm can guarantee a resolution in a reasonable time (bounded by a polynomial in their size). Here we explore algorithms for solving the number partitioning problem, and find that the fiendishly difficult cases arise near a phase transition.

Read directions and background in

• Number partitioning exercise.
• Lecture on NP-completeness, computational complexity, and phase transitions

All necessary files are linked at the left. Both Python and Mathematica versions of the hints files are given.