Normal view MARC view

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

Author: Yücesan, Enver ; Jacobson, SheldonINSEAD Area: Technology and Operations Management Series: Working Paper ; 92/11/TM Publisher: Fontainebleau : INSEAD, 1992.Language: EnglishDescription: 22 p.Type of document: INSEAD Working Paper Online Access: Click here Abstract: 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
Tags: No tags from this library for this title. Add tag(s)
Log in to add tags.
Item type Current location Collection Call number Status Date due
INSEAD Working Paper Digital Library
PDF Available

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

Digitized

There are no comments for this item.

Log in to your account to post a comment.
Koha 3.18 - INSEAD Library Catalogue
Library Home | Contact Us | What's Koha?