Resource title

On the intractability of verifying structural properties of discrete event simulation models

Resource image

image for OpenScout resource :: On the intractability of verifying structural properties of discrete event simulation models

Resource description

This paper presents an application of the theory of computational complexity to assess the difficulty of discrete event simulation modelling questions. The problem of verifying structural properties of discrete event simulation models is intractable. More specifically, accessibility of states, ordering of events, ambiguity of model implementations, and execution stalling are shown to be NP-complete decision problems. These results imply that it is unlikely that a polynomial-time algorithm can be devised to verify these structural properties of models. The consequences of these assertions cover a wide range of modelling and analysis questions in simulation. For instance, a general polynomial-time algorithm cannot be constructed to answer certain questions related to model validation and verification. At best, one can rely on rules of thumb or problem-specific procedures

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

application/pdf

Resource resource URL

http://flora.insead.edu/fichiersti_wp/Inseadwp1992/92-11.pdf

Resource license

Copyright INSEAD. All rights reserved