The System Design Process
Cannot Produce Optimal Systems

Terry Bahill
Systems and Industrial Engineering
University of Arizona
Tucson, AZ 85721-0020, USA
terry@sie.arizona.edu
http://www.sie.arizona.edu/sysengr/slides/np-complete
© 1998-2004 Bahill

System design is the process used to transfer the need for a system into an actual production unit. 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 will prove that this system design process is NP-complete (meaning it is very difficult). This will be done by restricting the Knapsack problem, which is known to be NP-complete to an instance of the system design process. The implications of this are that designing optimal systems with deterministic, polynomial time procedures is not possible. However, designing pretty good systems is possible and even likely. We will also show how the tools of operations research that are used to solve NP-complete problems can be applied to system design.

Reference: [68 and 80]. If this talk and "Metrics and Case Studies for Evaluating Engineering Designs" are both to be given, then this talk should come second. This lecture is suitable for systems engineers, computer scientists and operations researchers. This talk requires an overhead projector (or PowerPoint and a computer projection system). This talk takes one-half hour.