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?
-
$\begingroup$ 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. $\endgroup$– Giorgio CameraniSep 9, 2010 at 9:09
-
$\begingroup$ 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? $\endgroup$– Giorgio CameraniSep 9, 2010 at 9:49
2 Answers
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).
-
$\begingroup$ OK, hence my definition is just a special case of yours. In my definition the bound is 1, while in yours it is generic. $\endgroup$ Sep 9, 2010 at 14:43
-
$\begingroup$ @Kaveh, the definition you provided is equivalent to my definition since Hamming distance defines a metric space. $\endgroup$ Sep 9, 2010 at 15:03
-
$\begingroup$ @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. $\endgroup$ Sep 9, 2010 at 16:05
-
$\begingroup$ 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". $\endgroup$ Sep 9, 2010 at 16:08
-
$\begingroup$ 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. $\endgroup$– KavehSep 9, 2010 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.
-
$\begingroup$ 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"). $\endgroup$ Sep 9, 2010 at 13:57
-
$\begingroup$ The solution space is in n-dimensions and this is the reason for using the term Ball. $\endgroup$ Sep 9, 2010 at 14:15
-
$\begingroup$ I didn't catch the connection. Could you please explain further? $\endgroup$ Sep 9, 2010 at 14:23
-
$\begingroup$ For instance, in 3D, How do you define "left" or "right" around the center of a sphere? (which is a symmetric object) $\endgroup$ Sep 9, 2010 at 14:27
-
$\begingroup$ 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". $\endgroup$ Sep 9, 2010 at 14:37