×

Self-similarity of satisfiable Boolean expressions deciphered in terms of graph directed iterated function systems. (English) Zbl 1155.68079

Summary: The decision problem of satisfiability of a Boolean expression in \(k\)-conjunctive normal form (\(k\)SAT) is a typical NP-complete problem. In this paper, by mapping all Boolean expressions in \(k\)-conjunctive normal form onto a unit hypercube, we visualize the problem space of \(k\)SAT. The pattern of \(k\)SAT is shown to have self-similarity which can be deciphered in terms of a graph directed iterated function system. We show that the Hausdorff dimension of the pattern of \(k\)SAT is equal to the box-counting dimension and increases with \(k\). This suggests that the time complexity of \(k\)SAT increases with \(k\).

MSC:

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1016/S0304-3975(00)00168-7 · Zbl 0949.68148 · doi:10.1016/S0304-3975(00)00168-7
[2] DOI: 10.1016/S0304-3975(00)00280-2 · Zbl 0983.68100 · doi:10.1016/S0304-3975(00)00280-2
[3] DOI: 10.1017/S0004972700022243 · Zbl 0952.54029 · doi:10.1017/S0004972700022243
[4] DOI: 10.1142/S021812740400979X · Zbl 1057.28003 · doi:10.1142/S021812740400979X
[5] DOI: 10.1016/j.na.2003.08.001 · Zbl 1068.47065 · doi:10.1016/j.na.2003.08.001
[6] DOI: 10.1016/0304-3975(94)00049-O · Zbl 0873.68110 · doi:10.1016/0304-3975(94)00049-O
[7] DOI: 10.1006/inco.2000.2912 · Zbl 1007.68096 · doi:10.1006/inco.2000.2912
[8] DOI: 10.1006/inco.1995.1096 · Zbl 0834.58029 · doi:10.1006/inco.1995.1096
[9] Y. Sato, M. Taiji and T. Ikegami, Unconventional Models of Computation, eds. C. S. Calude, J. Casti and M. J. Dineen (Springer-Verlag, 1998) pp. 352–370.
[10] DOI: 10.1016/S0010-4655(99)00278-7 · doi:10.1016/S0010-4655(99)00278-7
[11] DOI: 10.1007/978-1-4757-4134-6 · doi:10.1007/978-1-4757-4134-6
[12] DOI: 10.1017/CBO9780511810817 · Zbl 0576.15001 · doi:10.1017/CBO9780511810817
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.