To Joe D I would say that perhaps complexity is more a state of one's mind than hard true fact. I know some folks who find a game like WitP to me not vary complex at all. A game like WitP has great depth and many factors and things that one must do each turn or 2 (depending on how often you stop to give orders)before you push that end turn button.
There is to my way of thinking not a great deal of game innovation in WitP but a great deal of detail handled by routines that are not that much state of the art, so to speak. Its not so much the game mechanic's that make it complex but rather the shear number of things going on in the game itself that make it that way. It is the way the game is designed that makes it complex but still allow one to be play it.
it WitP I finf that one can play a great bit of history such as the war in the pacific without becoming totally weighted down by it makes it such a great game experience.
To me it is large...yes. deep...yes, hard....perhaps but complex by its size and scope. You do what you need to do and just start it in motion and marvel at how it works...kind of like life. I don't worry about the small stuff like the best altitude for a particular aircraft or the best way to do something in the game. I do it and if it doesn't work I try something else kind of like life (OOPS I daid that already

)
So in the end complex is more to do with the way we see something rather than it being a fact. What I see as complex someone else may not. All games that are greater than a certain level to me are complex and require a longer learning curve for me. For someone else it might be be games I find complex they might find easy.
Well enough rambling on here I most likely have you (and myself) a bit confused. I write stuff like this all the time just for fun.

.
Yours,
Madgamer