Proofs of Existence and Optimality · Proofs of Nonexistence

Lesson 3

Nikolai Chukhin · Alexander S. Kulikov

The sets \(\{ 1, 2, 3 \}\) and \(\{1, 2, 3, 4, 5, 7\}\) can be split: \(1+2=3\) and \(4+7=1+2+3+5\). In the remaining three cases, it is not possible, and each time the reason is different:

  • the sum of the numbers in the set \(\{1, 2, 3, 4, 5, 6\}\) is odd;

  • in the set \(\{2, 4, 6, 8, 10, 12 \}\) the sum of the numbers is even, but it is obtained from the previous set by doubling all the numbers;

  • the set \(\{1, 2, 3, 4, 5, 17 \}\) has a number that is too large.

For the curious 🤓
We have seen three different obstacles that prevent splitting a set of numbers into two sets with equal sums. Naturally, one might ask: is there such an exhaustive list of obstacles? Unfortunately, we still do not know the answer to this question. If such a list of (easily checkable) obstacles existed, we could solve the corresponding problem, known as the knapsack problem, algorithmically quickly. At the same time, no one knows whether a fast algorithm for this problem exists or not. The question of the existence of such an algorithm is the question of the equality of the complexity classes \(\sf{P}\) and \(\sf{NP}\). This is one of the most important open questions in computer science and mathematics. The Clay Mathematics Institute has offered a prize of one million dollars for its solution.