# SAT Solution Space - Definition of Cluster of Solutions

I'm looking for a formal definition of Cluster of Solutions. My current understanding is the following. Let $x$ be a boolean assignment on $n$ variables. Let $f: \{ 0,1 \} ^n \to \mathbb{N}$ be a function that, given a boolean assignment $x$ on $n$ variables, just returns the natural number $i \in [0, 2^n-1]$ corresponding to $x$. Let $g: \mathbb{N} \to \{ 0,1 \} ^n$ be the inverse of $f$: given a natural number $i$, $g$ returns the corresponding solution (i.e. the binary encoding of $i$ in $n$ bits). Now, a Cluster of Solutions is a set $S$ of solutions such that, for each solution $x \in S$ and for each solution $y \in S$, it's the case that $g(i) \in S$ for each $i \in (f(x), f(y))$. Less formally, a Cluster of Solutions is a set whose solutions are "packed", i.e. "there are no non-solutions among the solutions". Is this definition correct?

• The latex code worked in the preview (except for curly braces in the definitions of the functions), while now it doesn't work at all. Sep 9 '10 at 9:09
• Magically, now it works again (I didn't do anything). But the curly braces are still not rendering: does anybody know how to display them? Sep 9 '10 at 9:49

I think a cluster of solutions is a maximal set of solutions $T$ s.t. you can reach every $\tau' \in T$ from every other $\tau \in T$ by a sequence of solutions $\{\tau_i\}_{0\leq i\leq n}$ ($\tau = \tau_0$ and $\tau' = \tau_n$) where the hamming distance between each consecutive pair of solutions is bounded, i.e. they are just connected components in the graph where two solutions are adjacent iff the hamming distance between them is less than the bound.

See these notes by Dimitris Achlioptas (or papers on statistical physics and random k-SAT).

• OK, hence my definition is just a special case of yours. In my definition the bound is 1, while in yours it is generic. Sep 9 '10 at 14:43
• @Kaveh, the definition you provided is equivalent to my definition since Hamming distance defines a metric space. Sep 9 '10 at 15:03
• @Walter Bishop: Your definition does not imply the connectedness by Hamming distance 1, nor is it implied by the connectedness by Hamming distance 1. For the first claim, consider the Hamming distance between g(2^{n−1}−1) and g(2^{n−1}). For the second claim, consider a set {000, 100, 010, 001}. @turkistany: It is not equivalent. Consider the set of n-bit strings whose parity is even. Sep 9 '10 at 16:05
• The more general definition given by Kaveh seems to induce a "subjective" flavour to clusters: a set of solutions is or is not a cluster depending on the bound k we are willing to tolerate. So maybe the right term to use is "k-cluster", instead of simply "cluster". Sep 9 '10 at 16:08
• I think the bound (which does not need to be constant ad can depend on the number of variables) depends on the application. The main point is reaching another solution in the cluster is easy, you don't need to flip lots of bits, therefore you can do a local search. If I remember correctly, in the difficult phase of random k-SAT (when clause density is restricted to a specific range) the distance between different clusters is linear in $n$, and it is difficult to find a solution by picking a random assignment $\tau$ and doing a local search around it. Sep 9 '10 at 16:22

I think a possible alternative for solution cluster definition could be the folowing:

solution cluster is a set of satisfying Boolean assignments inside a ball of some given radius. The distance metric is Hamming distance between two satisfying assignments. This would enable a compact representation of each cluster by giving the center and the radius of the cluster.

• This is a nice and compact definition. I have only one concern: what if our cluster is composed by an even number of solutions? In such a case we don't have a very center: this would cause us to include 1 more solution which actually doesn't belong to the cluster (we overshoot either "on the left" or "on the right"). Sep 9 '10 at 13:57
• The solution space is in n-dimensions and this is the reason for using the term Ball. Sep 9 '10 at 14:15
• I didn't catch the connection. Could you please explain further? Sep 9 '10 at 14:23
• For instance, in 3D, How do you define "left" or "right" around the center of a sphere? (which is a symmetric object) Sep 9 '10 at 14:27
• What I meant with "left" and "right" was just intuitive and non-rigorous. Imagine a binary tree of depth n: it represents all the possible assignments on n variables. You can draw such binary tree on a 2D sheet. Given a leaf x, it's easy to see which leaves are on its "left" and which leaves are on its "right". Sep 9 '10 at 14:37