Recognizing Sumsets is NP-Complete

Amir Abboud, Nick Fischer, Ron Safier +1

Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set $S$ is a sumset, i.e. whether there is a s…