DocumentCode :
3125516
Title :
Complexity of the system design problem
Author :
Chapman, W.L. ; Rozenblit, J.
Author_Institution :
Hughes Aircraft Co., Tucson, AZ, USA
fYear :
1995
fDate :
1995
Firstpage :
51
Lastpage :
57
Abstract :
The system design problem describes the process used to translating the need or requirements for a system into an actual design. It requires selecting components from a given set and matching the interfaces between them. Those that can be connected to meet the top-level system´s input and output requirements are tested to see how well they meet the system´s performance and cost goals. We prove that this system design process is NP-complete by restricting the knapsack problem, which is known to be NP-complete, to an instance of the system design process problem. The results indicate that designing optimal systems with deterministic, polynomial-time procedures is not possible.
Keywords :
computability; computational complexity; operations research; optimal systems; systems analysis; NP-complete process; components selection; cost goals; deterministic polynomial-time procedures; input requirements; interface matching; knapsack problem; optimal systems design; output requirements; performance goals; requirements engineering; system design problem complexity; top-level system; Aircraft; Costs; H infinity control; NP-complete problem; Polynomials; Set theory; System performance; System testing; Time measurement;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Systems Engineering of Computer Based Systems, 1995., Proceedings of the 1995 International Symposium and Workshop on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-7803-2531-1
Type :
conf
DOI :
10.1109/ECBS.1995.521840
Filename :
521840
Link To Document :
بازگشت