Let N be a set of nonnegative integers (amen!). We say that N has the decomposition property if there are nonempty subsets N1 and N2, maybe overlapping or identical but both containing at least two elements, such thatThe source of this question is a paper by Mateesca, Salomaa and Yu.
N = { n1 + n2 | n1 ∈ N1 and n2 ∈ N2}.
Can we find such two subsets for a given N or it's NP-complete?
I found this question interesting because we know that if N indeed had such a structure, and we were presented N1 and N2 instead, we could rank and select elements from N far more efficiently than if we had N itself.