デザィン問題の計算複雑性: デザィン問題を解くアルゴリズムはNP完全である

摘要

デザィンを問題解決として捉えるとデザィン問題は充足問題として定式化できるということを示し，充足問題がNP完全問題であることを踏まえてデザィン問題の性質を考察した.%It is shown that design can be formulated as satisfiability problem solving, or SAT ， if we regard design as a purposive activity to solve a problem. Some characteristics of design computation are disccued on the basis of Cook's Theorem saying that SAT is NP-complete problem and the characteristics of NP-complete problem. It is possible to determine whether a certain design product is actually a solution of a design problem or not in polynomial time. This implies that generate and test is one of pragmatic approaches to solve a design problem if the computational complexity of the algorithm of generating a design product is in the class of pronominal time. It is an important task for design computing study to find such a generation algorithm and to construct a computational model of design thinking where promising design products are created.