NP-completeness of kSAT and multifractals

The geometrical structure of a formal language class is studied in relation with its time-complexity. A typical NP-complete problem, kSAT, is discusse d by visualizing its problem space and a strict connection is made between the self-similarity and the time-complexity of the languages by constructin g adequate iterated function systems (IFSs), There exist IFS classes which generate whole satisfiable Boolean expressions embedded on a unit hyper-cub e, Our numerical results for the Hausdorff dimension of kSAT suggest the di fference of IFS classes for 2 and 3SAT. (C) 1999 Elsevier Science B.V. All rights reserved.