Yes I know what complexity theory is referring to. What I mean is in an environment like DOS 2, where the game is turn-based and actual possibilities fall within a very limited context, the pressure to compute things quickly is not as important or as hard as say, formulating sentences and communicating with people in real time without them figuring out you are a robot. And I'd argue that having a deterministic system is exactly a way to facilitate easier AI development. You are making it easier to have perfect prediction on the result of each action after all.
