FRACTAL STRUCTURE ON k-SAT
Qin Wang, Lifeng Xi · Fractals · 2011
The k-SAT (k ≥ 3) is a typical NP-complete problem in computer science. To visualize k-SAT, we embed the Boolean expressions in k-CNF, with variables in an infinite list, into cube [0, 1]k of Euclidean space. In this paper, we find fractal structure of the visualized image of satisfiable expressions, we also prove that the image has full Hausdorff dimension k under some reasonable condition, by constructing some Moran subset. The results show this image is quite different from that with respect to a finite list of Boolean variables as in Refs. 1 and 2.