This special issue of the Journal of Membrane Computing is devoted to complexity in two of its aspects. On the one hand, the study of computational complexity theory in the framework of membrane computing, giving efficient solutions to presumably intractable problems, and finding frontiers of efficiency. On the other hand, the area of complex systems is very important nowadays for all its applications from physics to social sciences, passing by a vast number of fields such as engineering, biology, chemistry and so on.