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.

1 comment:

  1. I'm sorry this question is not directly about this post or even about geometry in general, but a commenter on my weblog ( had a question regarding whether it was insulting to call ACK a 'graphic novel', whether it would be more accurate to call it a 'graphic epic'. Since you had more intimate knowledge about ACK than I do, I was hoping you would be so kind as to drop a response about how you felt.


Disqus for The Geomblog