Recursive operations are common procedures in the fields of computational theory and fractal geometry. Recently, computational theory has paid much attention to fractal geometry. In this paper, the geometrical structure of a formal language class is studied in relation with its time-complexity. A typical NP-complete problem, kSAT, is discussed by visualizing its problem space. A strict connection is made between the self-similarity and the time-complexity of the languages by constructing adequate iterated function systems (IFSs). There exist IFS classes which generate whole satisfiable Boolean expressions embedded on a unit hyper-cube. The difference in time-complexity between 2SAT and 3SAT is connected to IFS classes which generate satisfiable Boolean expressions. That is, the class P complexity is related to what we call monotone IFS and the class NP or upper complexity does to more complex IFS. Our numerical results for the Hausdorff dimension of satisfiable Boolean expressions suggest the difference of IFS classes between 2 and 3SAT.
展开▼
