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

Sheldon H. Jacobson and Enver Yücesan
Additional contact information
Sheldon H. Jacobson: University of Illinois at Urbana-Champaign, Urbana, Illinois
Enver Yücesan: INSEAD, Fontainebleau Cedex, France

Operations Research, 1999, vol. 47, issue 3, 476-481

Abstract: 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.

Keywords: simulation; modeling; validation; verification; computational complexity (search for similar items in EconPapers)
Date: 1999
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.47.3.476 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:47:y:1999:i:3:p:476-481

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().