"complexity, n. Add: [2.] c. Math. More fully computational complexity. A measure of the difficulty of solving a class of problem, as measured by the expected number of computational steps required to do so using an algorithm; the branch of computational theory concerned with this property."
Oxford English Dictionary, 2002
2. Complexity is being marked by an involvement of many parts, aspects, details, notions, and necessitating earnest study or examination to understand or cope with (Webster's Third International Dictionary; Klir, 1985).
3. Complexity has many varied interrelated parts, patterns, or elements and consequently is hard to understand fully (Klir, 1985).
4. Complexity is the lack of connectedness in the system (Casti, 1992).
5. "In general, we seem to associate complexity with anything we find difficult to understand." (Flood and Carson, 1993).
6. Complexity is a perceived systems attribute which increases as the number and variety of elements and relationships within the system becomes greater, and increases as the level of predictability and understanding of the system as a whole decreases (McCarthy, 1995)."
Skeptics Society: A Quick & Dirty Guide To Chaos And Complexity Theory