System design is an NP-complete problem

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

Research output: Contribution to journalArticlepeer-review

32 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)222-229
Number of pages8
JournalSystems Engineering
Issue number3
StatePublished - 2001

ASJC Scopus subject areas

  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'System design is an NP-complete problem'. Together they form a unique fingerprint.

Cite this