In this paper we study the Subset Sum Problem (SSP). Assuming the SSP has at most one solution, we provide a randomized quasi-polynomial algorithm which if the SSP has no solution, the algorithm always returns FALSE while if the SSP has a solution the algorithm returns TRUE with probability $\frac{1}{2^{\log(n)}}$. This can be seen as two types of coins. One coin, when tossed always returns TAILS while the other also returns HEADS but with probability $\frac{1}{2^{\log(n)}}$. Using the Law of Large Numbers one can identify the coin type and as such assert the existence of a solution to the SSP. The algorithm is developed in the more general framework of maximizing the distance to a given point over an intersection of balls.

翻译：暂无翻译