Friday, November 26, 2004

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 N1 and N2, maybe overlapping or identical but both containing at least two elements, such that

N = { n1 + n2 | n1N1 and n2N2}.

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 N1 and N2 instead, we could rank and select elements from N far more efficiently than if we had N itself.

Disqus for The Geomblog