Summary: We suggest here an algorithm based on stickers for the DNA computing model [S. Roweis et al., “A sticker-based model for DNA computation”, Discrete Math. Theor. Comput. Sci. 44, 1–29 (1999; Zbl 0919.68027)] that solves the well-known Bin-Packing Problem (BPP), that belongs to the class of NP-hard problems in the strong sense, in time bounded by , where is the quantity of items and the space requirements expressed in bits.
To the best of the authors’ knowledge, this is the first polynomial-time algorithmic solution for BPP in such a model.