The computational complexity of component selection in simulation reuse

Simulation composability has been much more difficult to realize than some initially imagined. We believe that success lies in explicit considerations for the adaptability of components. In this paper, we show that the complexity of optimal component selection for adaptable components is NP-complete...

Full description

Saved in:
Bibliographic Details
Main Authors: Bartholet, R.G., Brogan, D.C., Reynolds, P.F.
Format: Conference Proceeding
Language:English
Subjects:
Buildings
Computational complexity
Computational modeling
Computer science
Computer simulation
Cost function
Polynomials
Real time systems
Research initiatives
Software engineering
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Simulation composability has been much more difficult to realize than some initially imagined. We believe that success lies in explicit considerations for the adaptability of components. In this paper, we show that the complexity of optimal component selection for adaptable components is NP-complete. However, our approach allows for the efficient adaptation of components to construct a complex simulation in the most flexible manner while allowing the greatest opportunity to meet all requirements, all the while reducing time and costs. We demonstrate that complexity can vary from polynomial, to NP, and even to exponential as a function of seemingly simple decisions made about the nature of dependencies among components. We generalize these results to show that regardless of the types or reasons for dependencies in component selection, just their mere existence makes this problem very difficult to solve optimally.
ISSN:0891-7736
1558-4305
DOI:10.1109/WSC.2005.1574541