NP-completeness of kSAT and multifractals Original Research Article

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 and 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. Our numerical results for the Hausdorff dimension of kSAT suggest the difference of IFS classes for 2 and 3SAT.