<p>I think a possible alternative for solution cluster definition could be the folowing:</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-09T13:57:10.130Z
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").
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T14:15:02.390Z
The solution space is in n-dimensions and this is the reason for using the term Ball.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-09T14:23:24.373Z
I didn't catch the connection. Could you please explain further?
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T14:27:30.890Z
For instance, in 3D, How do you define "left" or "right" around the center of a sphere? (which is a symmetric object)
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-09T14:37:50.630Z
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".
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T14:44:35.330Z
It is possible in your definition of cluster.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-09T14:50:53.723Z
Yes, in my definition a solution x is on the "left" of a solution y if and only if f(x) < f(y).
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T13:25:37.813Z
2010-09-09T13:25:37.813Z
Mohammad Al-Turkistany
<p>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.</p>

<p>See <a href="http://michaelnielsen.org/polymath1/index.php?title=Random_k-SAT">these notes</a> by Dimitris Achlioptas (or papers on <em>statistical physics</em> and <em>random k-SAT</em>).</p>

CC BY-SA 2.5
2010-09-09T14:43:04.397Z
OK, hence my definition is just a special case of yours. In my definition the bound is 1, while in yours it is generic.
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T15:03:16.437Z
@Kaveh, the definition you provided is equivalent to my definition since Hamming distance defines a metric space.
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-09-09T16:05:24.913Z
@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.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-09T16:08:03.320Z
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".
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T16:22:56.023Z
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.
Kaveh
CC BY-SA 2.5
2010-09-09T16:24:43.493Z
[continued] Take a look at papers of Dimitris Achlioptas from 2008: http://users.soe.ucsc.edu/~optas/
Kaveh
CC BY-SA 2.5
2010-09-09T16:27:47.357Z
@Tsuyoshi Ito: Thanks, you're right. So both my first and second comments here are wrong. I'm going to remove them. Now the question is: which of the 2 definitions is more adequate to model our intuitive feeling of the meaning of "cluster"?
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T16:44:01.103Z
@Kaveh: Thanks for the pointer: I'll take a look at those papers. I feel that my definition is affected by a weakness, but it's still not clear to me which is such weakness.
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T17:19:36.643Z
@Walter Bishop: You are welcome. Just be careful because it seems that the word "cluster" already has an established meaning in the literature, so using another definition can be confusing for others.
Kaveh
CC BY-SA 2.5
2010-09-11T21:37:10.900Z
@Walter Bishop: “which of the 2 definitions is more adequate to model our intuitive feeling of the meaning of "cluster"?”  It depends on what you want to use the notion for.  Note that a “cluster” is a geometric notion in that it groups “close” solutions together.  If there is a reason to view truth assignments as binary numbers, your definition will be more natural.  If not, truth assignments are just bit strings and the Hamming distance is a natural distance among them.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-11T21:39:26.480Z
@Walter Bishop: (cont’d)  As a separate matter, as Kaveh says, the term “cluster” is already used in the literature, so if you want to give a name to a different notion, probably it is better to use a different name.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-13T10:37:49.637Z
@All: The original intent of my question was to understand if my intuitive notion of "cluster" corresponded or not to the meaning of "cluster" in the literature. I didn't want to change the definition of a well established and universally accepted term! Now it's clear that what I understood to be a cluster is different than its correct meaning in literature. I was driven to such an intuition by visualizing the solution space as a binary tree, and considering each group of contiguous leaves to be a cluster. Then I realized that my definition depends on a specific variable ordering...
Giorgio Camerani
CC BY-SA 2.5
2010-09-13T10:43:27.180Z
@All: (cont'd) ...and so it lacks of generality. Moreover, as pointed out by Tsuyoshi Ito, it doesn't imply h = 1 nor is implied by h = 1. Maybe mine is the definition of a "visual cluster", or of a "leaf cluster". What I find "strange" from an intuitive or visual point of view is that you can have 2 leaves in the binary tree which are close one another (and so they form a "leaf cluster") but whose hamming distance is greater than 1 (and so they don't form a 1-cluster).
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T14:29:00.987Z
2010-09-09T14:29:00.987Z
Kaveh
<p>I'm looking for a formal definition of <b>Cluster of Solutions</b>. 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 <b>Cluster of Solutions</b> 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 <b>Cluster of Solutions</b> is a set whose solutions are "packed", i.e. "there are no non-solutions among the solutions". Is this definition correct? </p>

CC BY-SA 2.5
2010-09-09T09:09:47.997Z
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.
Giorgio Camerani
CC BY-SA 2.5
2010-09-09T09:49:23.533Z
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?
Giorgio Camerani
<cc.complexity-theory><sat>
SAT Solution Space - Definition of Cluster of Solutions
Giorgio Camerani
# SAT Solution Space - Definition of Cluster of Solutions

(Asked by: username_0 on 2010-09-09)

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?

**Tags:** cc.complexity-theory, sat

> **Comments:**
> **username_0**: 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.  
> **username_0**: 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?  

---

## 2 answers

### Answer by username_2 on 2010-09-09. Score: 6 | Accepted answer

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](http://michaelnielsen.org/polymath1/index.php?title=Random_k-SAT) by Dimitris Achlioptas (or papers on *statistical physics* and *random k-SAT*).

> **Comments:**
> **username_0**: OK, hence my definition is just a special case of yours. In my definition the bound is 1, while in yours it is generic.  
> **username_1**: @username_2, the definition you provided is equivalent to my definition since Hamming distance defines a metric space.  
> **username_3**: @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.  
> **username_0**: The more general definition given by username_2 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".  
> **username_2**: 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.  
> **username_2**: [continued] Take a look at papers of Dimitris Achlioptas from 2008: http://users.soe.ucsc.edu/~optas/  
> **username_0**: @username_3: Thanks, you're right. So both my first and second comments here are wrong. I'm going to remove them. Now the question is: which of the 2 definitions is more adequate to model our intuitive feeling of the meaning of "cluster"?  
> **username_0**: @username_2: Thanks for the pointer: I'll take a look at those papers. I feel that my definition is affected by a weakness, but it's still not clear to me which is such weakness.  
> **username_2**: @Walter Bishop: You are welcome. Just be careful because it seems that the word "cluster" already has an established meaning in the literature, so using another definition can be confusing for others.  
> **username_3**: @Walter Bishop: “which of the 2 definitions is more adequate to model our intuitive feeling of the meaning of "cluster"?”  It depends on what you want to use the notion for.  Note that a “cluster” is a geometric notion in that it groups “close” solutions together.  If there is a reason to view truth assignments as binary numbers, your definition will be more natural.  If not, truth assignments are just bit strings and the Hamming distance is a natural distance among them.  (more)  
> **username_3**: @Walter Bishop: (cont’d)  As a separate matter, as username_2 says, the term “cluster” is already used in the literature, so if you want to give a name to a different notion, probably it is better to use a different name.  
> **username_0**: @All: The original intent of my question was to understand if my intuitive notion of "cluster" corresponded or not to the meaning of "cluster" in the literature. I didn't want to change the definition of a well established and universally accepted term! Now it's clear that what I understood to be a cluster is different than its correct meaning in literature. I was driven to such an intuition by visualizing the solution space as a binary tree, and considering each group of contiguous leaves to be a cluster. Then I realized that my definition depends on a specific variable ordering...  
> **username_0**: @All: (cont'd) ...and so it lacks of generality. Moreover, as pointed out by username_3, it doesn't imply h = 1 nor is implied by h = 1. Maybe mine is the definition of a "visual cluster", or of a "leaf cluster". What I find "strange" from an intuitive or visual point of view is that you can have 2 leaves in the binary tree which are close one another (and so they form a "leaf cluster") but whose hamming distance is greater than 1 (and so they don't form a 1-cluster).  

---

### Answer by username_1 on 2010-09-09. Score: 3

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.

> **Comments:**
> **username_0**: 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").  
> **username_1**: The solution space is in n-dimensions and this is the reason for using the term Ball.  
> **username_0**: I didn't catch the connection. Could you please explain further?  
> **username_1**: For instance, in 3D, How do you define "left" or "right" around the center of a sphere? (which is a symmetric object)  
> **username_0**: 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".  
> **username_1**: It is possible in your definition of cluster.  
> **username_0**: Yes, in my definition a solution x is on the "left" of a solution y if and only if f(x) < f(y).  

---

