An interesting problem:

emmous asks an interesting question:

Let N be a set of nonnegative integers (amen!). We say that N has the decomposition property if there are nonempty subsets N₁ and N₂, maybe overlapping or identical but both containing at least two elements, such that

N = { n₁ + n₂ | n₁ ∈ N₁ and n₂ ∈ N₂}.

Can we find such two subsets for a given N or it's NP-complete?

The source of this question is a paper by Mateesca, Salomaa and Yu.

I found this question interesting because we know that if N indeed had such a structure, and we were presented N₁ and N₂ instead, we could rank and select elements from N far more efficiently than if we had N itself.