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

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