It has been ages since an NP-completeness result has drawn much attention, but an exception is due this time, given the nature of the computational problem. Specifically, for a group $G$, given a set $S$, the task is to decide whether or not there exists a set $A$ such that $S=A+A$, where $A+A=\{a+b:a,b\in A\}$.
The hardness result is shown both for any group consisting of a vector space over a prime field and for the integers. In the latter case, the reduction uses (positive) numbers of logarithmic description length (equiv., polynomial size). The reduction from 3SAT is parsimonious: Given a 3CNF $\phi$, it produces a set $S_\phi$ as well as a set $V_\tau$ for each assignment $\tau$ to $\phi$ such that $S_\phi = V_\tau + V_\tau$ if and only if $\tau$ satisfies $\phi$ (and there are no other $V$'s that solve $V+V=S_\phi$).
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 set A such that A+A=S. Granville suggested an algorithm that takes exponential time in the size of the given set, but can we do polynomial or even linear time? This basic computational question is indirectly asking a fundamental structural question: do the special characteristics of sumsets allow them to be efficiently recognizable? In this paper, we answer this question negatively by proving that the problem is NP-complete. Specifically, our results hold for integer sets and over any finite field. Assuming the Exponential Time Hypothesis, our lower bound becomes exp(n^{1/4}).
See ArXiv 2410.18661.