System design is an NP‐complete problem

William L. Chapman, Jerzy Rozenblit and A. Terry Bahill

Systems Engineering, 2001, vol. 4, issue 3, 222-229

Abstract: The system design process translates the customers' needs into a buildable system design. It requires selecting subsystems from an allowable set and matching the interfaces between them. Designs that meet the top‐level input and output requirements are tested to see how well they meet the system's performance and cost goals. This paper proves that the System Design Problem is NP‐complete by reduction from the Knapsack Problem, which is known to be NP‐complete. The implication of this proof is that designing optimal systems with deterministic, polynomial time procedures is not possible. This is the primary reason why engineers do not try to produce optimal systems: They merely produce designs that are good enough. © 2001 John Wiley & Sons, Inc. Syst Eng 4: 222–229, 2001

Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/sys.1018

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:wly:syseng:v:4:y:2001:i:3:p:222-229

Access Statistics for this article

More articles in Systems Engineering from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().