Implementation of reasoning and planning frameworks covering both the iterated modalities needed for plan-based dialogue behavior and the realities of a task domain has proved feasible for constrained dialogues in restricted domains (e.g., Smith et al. 1995), but quickly comes up against a complexity barrier when the coverage of language and the scope of the domain of discourse are enlarged. Planning is in general NP-hard, indeed PSPACE-complete even in propositional planning formalisms (Bylander 1994), and plan recognition can be exponential in the number of goals to be recognized, even if all plans available for achieving the goals are known in advance (Geib 2004).