This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Jacobson, S. H. Articles by Yücesan, E. Search for Related Content

On the Complexity of Verifying Structural Properties of Discrete Event Simulation Models

University of Illinois at Urbana-Champaign, Urbana, Illinois
INSEAD, Fontainebleau Cedex, France

This paper uses computational complexity theory to assess the difficulty of various discrete event simulation problems. More specifically, accessibility of states, ordering of events, noninterchangeability of model implementations, and execution stalling for discrete event simulations are formally stated as search problems and proven to be NP-hard. The consequences of these results cover a wide range of modeling and analysis problems in simulation. For example, problems associated with certain variance reduction techniques, model verification, model validation, and the applicability of infinitesimal perturbation analysis, among others, are deemed intractable.

Subject classifications: simulation; modeling; validation; verification; computational complexity.