We study counting problems that are related to the analysis of nanostructures. Those counting problems have the following fundamental feature: all those problems are sparse problems and cannot be NP-hard. This implies that we cannot apply the basic concepts and tools of complexity theory to analyze those problems.

We have proven some intractability results, as well as some tractability results. The latter are related to the logtime computability of counting and optimization problems related to nanotubes and one-dimensional lattices. Those results are based on, and also extend, a well known theorem of Buchi about the properties of labelled paths that can be defined in monadic second order logic.