Communications: A Proof of the Complexity of Design

The problem of design is to find the best mapping between specifications and a solution space. A key operation that is involved in the early stages of the design process is the synthesis operation. This short communication employs a framework previously published by the authors, to formulate a simple variant of the synthesis problem of the design. The problem is proved to be computationally intractable, thus leading to a practical conclusion that heuristics should be searched for.