What is a Complex Project?

We have different concepts of complexity. For someone who says "I'm not good with math!", finding the area of a simple, right triangle is complex. Sometimes complexity is about viewpoint ("I'm not good with math!"). Sometimes complexity is about your personal stress level (what causes you to experience stress). So what is Project complexity?
 

A Complex Project involves a network of numerous tasks* with a wide variety of interactions and inter-dependencies.

(* Although I've used "tasks", this could also be other Project elements - resources, people, locations, etc. I've used tasks generically under the assumption that even if the complexity is caused by numerous "locations", these are still represented by "task interactions and inter-dependencies".)

Mathematically, as the number of tasks grows, the number of possible interactions grows at a rapid rate. For a small number of tasks, say 3, we can easily write out the combinations that are possible: (a,b,c) (a,c,b) (b,a,c) (b,c,a) (c,a,b) (c,b,a). But, even at a small number like 3, we are reaching our limits of keeping track of the possibilities by memory. Expand that to 2,000 or 15,000 distinct tasks and we get a real feel for the meaning of complexity. Obviously, this explains why Projects with many tasks require sophisticated software for tracking schedule tasks and in most cases for cost tracking as well.

For Project work, the question of complexity also has to assume some base level of Project competence. Otherwise, we're debating the meaning of complexity. So, in the simple definition above, terms like "numerous" and "wide variety" have to have some boundaries.

If a Project involves a common set of sequential tasks that we've encountered numerous times, it's no longer truly complex for this discussion. Although we might not be able to mentally track all the combinations of tasks, we understand it from experience.

So, for a clearer definition, a truly complex Project must have some additional issues. The issue could be one of the following sets:

1. The set of tasks is an unfamiliar one. The unfamiliarity creates uncertainty about the results.
2. The tasks are familiar, and the results of a failure in the interactions is known to result in Project interruptions.
3. The task are familiar, the results of a failure are known, and the number of interactions is very large.

We could continue to expand that list but these are basic. So, if this is a Complex Project, what do we do to improve our leadership and management of a Project like this?