![](/files/happy5.png)
Problem Let
be natural numbers with
. It follows from the pigeon-hole principle that there exist distinct subsets
with
. Is it possible to find such a pair
in polynomial time?
![$ a_1,a_2,\ldots,a_n $](/files/tex/e7587d53923e6a1289b1a25bce813c459b94a973.png)
![$ \sum_{i=1}^n a_i < 2^n - 1 $](/files/tex/2e06c61586963020dafdeb383b019b8cf808f937.png)
![$ I,J \subseteq \{1,\ldots,n\} $](/files/tex/c7ef2d05312ea577dc99d5541b4d6f105c6241b5.png)
![$ \sum_{i \in I} a_i = \sum_{j \in J} a_j $](/files/tex/4a695b4ff5bea4e5166e5740755c25b9de83abaa.png)
![$ I,J $](/files/tex/540bdad470006e47258d2efec74f098ef7dea897.png)
This is one of a class of search problems for which a positive solution is garaunteed (so the corresponding decision problem is trivial) based on a theoretical property of the problem. Another such problem is given a Hamiltonian cycle in a cubic graph, find a second Hamiltonian cycle (here a theorem of Smith guarantee's a positive solution). The above problem is particularly attractive, since the proof that a pair must exist is quite simple, but it gives no insight into how to find the pair
.
It seems to be consensus among the cryptography community that this problem is hard.