What is a complex system?

Complex systems research is becoming ever more important in both the natural and social sciences. It is commonly implied that there is such a thing as a complex system across the disciplines. However, there is no concise definition of a complex system, let alone a definition that all disciplines agree on. We review various attempts to characterize a complex system, and consider a core set of features that are widely associated with complex systems by scientists in the field. We argue that some of these features are neither necessary nor sufficient for complexity, and that some of them are too vague or confused to be of any analytical use. In order to bring mathematical rigour to the issue we then review some standard measures of complexity from the scientific literature, and offer a taxonomy for them, before arguing that the one that best captures the qualitative notion of complexity is that of the statistical complexity. Finally, we offer our own list of necessary conditions as a characterization of complexity. These conditions are qualitative and may not be jointly sufficient for complexity. We close with some suggestions for future work