In my opinion, a game should only be considered as being 'complex' if it's 'solution-set' is hard to deduce as a result of high decision complexity. If a game merely grants the player a large amount of freedom for achieving an easily attainable goal, then the game isn't complex in my opinion and is merely a sandbox, irrespective of the game's rule complexity.
The problem with this attitude is that even the most complex (your definition) games can and will be broken down to optimal paths.
Take Aurora. If you understand how all of the interlocking systems of ship design function, you can build optimal ships for any given TL of challenge. The only difficulty at that point is pretty simple macro to boost your R&D and production enough to get to safe territory (~TL6) before one of the potential early game hazards (Swarm Queen on Earth before you can kill one, Invaders jumping into Sol, &c.) swats you. Aurora's not a complex game, just a game about being reasonably efficient with your economy, right?
It's not a "solved" game in the sense that existing chess-playing AI are fairly close to solving chess, but the known pool of high-efficiency strategies and tactics is small enough to make any efficient campaign broadly similar, distinguished only by the semi-random aspects and level of self-imposed challenge you take on.
For other examples, just about every classic game of any note has been broken down to a single most-efficient route by speedrunners, to the extent that for certain titles the only way of reasonably ensuring a faster record time is the discovery of a relevant and previously unknown exploit.
In brief, I disagree with your point, because
every game has simple enough goal-states that "winning" can be broken down into two things: whether the player took one of the optimal paths, and whether luck-based aspects fell in the player's favor. Given that optimal paths are fairly easy to determine with some trial and error, that would propose that complexity is solely derived from the presence and number of random and pseudo-random elements. It's a little reductive, but by that logic a digital slot machine would be the most complex game around since there's almost no way to optimize play.
There's also the question of how granular you want to be when defining the decision-making process. Touhou games, by one standard, are incredibly simple. Screen scroll, you hold fire and move around. From another standard, you're making hundreds of decisions per minute, each vital to your continued success. You can do the same thing for any game to get any outcome you want.
As far as I'm concerned, complexity isn't a value-statement to begin with. A game should have the appropriate level of complexity for what it is trying to do. Is checkers worse than chess because it's not as complex? Is chess worse than Stratego because it doesn't have the hidden pieces and bluffing element, or better because it has more complex piece interactions? Are both better or worse than Risk? Is Risk worthless because EUIV exists?