ON THE COMPLEXITY OF THE DESIGN SYNTHESIS PROBLEM

In this paper we present and analyze a formal model of a design proces s, emphasizing the synthesis part. The design artifact description is identified as an algebraic structure. The desired function and constra ints are mapped to the artifact description using an evolutionary proc ess that can be visualized as a feedback loop of analysis, synthesis a nd evaluation. A special case of the synthesis activity, called the Ba sic Synthesis Problem (BSP), is addressed. The BSP is shown to be NP-C omplete. As a consequence, tractability can be obtained by enforcing c onstraints on the artifact structure. As such, we present a model havi ng an element of descriptive design theory that is also a framework fo r the future development of computational support systems and automati c design tools.