I'd guess the complexity is dependent on the decision graph complexity: cyclic vs acyclic, entrance/exit points...
If it gets to conditional / puzzle evaluation that starts to get Turing Complete, then it will hit the halting problem, which I believe is thought to be noncomputable for nontrivial graphs / code.