Computational Requirements for Nano-Machines: There is Limited Space at the Bottom

Akyildiz et al. envisioned the use of nanonetworks as a new paradigm for computation on a very small scale. Since then, many scientists researched dependent aspects like nanoscale communication. However, most research omitted specifying the computational complexity required for their respective scenarios. To close this gap, we analyzed numerous medical scenarios and extracted the formal problems to be solved. We then compared the resulting formal problems using computational complexity theory and displayed them sorted into the classes AC 0, NC 1 and L. Lastly, we describe the benefits of our results for simulation purposes and to better assess the feasibility of nanonetwork scenarios.