The complexity of rapid learning in discrete event simulation

Sensitivity analysis and optimization of discrete event simulation models require the ability to efficiently estimate performance measures under different parameter settings. One technique, termed rapid learning, aims at enumerating all possible sample paths of such models. There are two necessary conditions for this capability: observability and constructability. This paper shows that the verification of the observability condition is an NP-hard search problem: this result encourages the development of heuristic procedures to validate the applicability of rapid learning. Further implications are also discussed.