The clustered Sparrow algorithm

arXiv:1804.11181 · cs.DS · Submitted 2018-04-30 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "The clustered Sparrow algorithm".

Paper summary: Tom: To wrap up the clustered Sparrow algorithm, we're seeing a way to solve three seven sat by transforming it into a two seven sat problem while keeping the same solution, and they established polynomial time bounds based on their stochastic local search and Markov chain analysis.

Jane: Right. The authors, Cristian Dumitrescu from Kitchener, are showing how you can bridge that gap between three seven sat and two seven sat efficiently by using this clustered Sparrow algorithm.

Lu: This work focuses on the idea of finding a two seven sat expression that has the same satisfying solution as the original three seven sat expression through stochastic local search, and they present arguments that this algorithm is polynomial.

Meng: I’m still thinking about how they handle those tracking requirements at scale, because if it requires constant updates to that associated two seven clause, the overhead could be substantial for production systems.

Lalam: The analysis suggests that even with those updates, the method manages it in a way that keeps things efficient enough for their time bounds.

Tom: So, what does this mean practically? It means we have a concrete way to approach these NP complete problems by using probabilistic methods and finding structural relationships between different problem sizes.

Jane: It means we have an algorithm that can handle the complexity of three seven sat by reducing the search space to two seven sat while maintaining correctness, which is a tangible result for solving hard constraint satisfaction problems.

Conclusion: Tom: So, to wrap up on the clustered Sparrow algorithm, they’re showing how you can solve three seven sat by turning it into a two seven sat problem while keeping that same satisfying solution, and they proved this whole search method is polynomial time using their local search and Markov chain analysis.

Jane: Exactly. The authors are Cristian Dumitrescu from Kitchener. It’s a clever way to look at these hard constraint satisfaction problems by simplifying the structure without losing the original answer you were looking for.

Lu: What this really means is that we have a concrete, probabilistic method that can find an equivalent two seven sat expression efficiently, and they manage to keep the same satisfying assignment throughout the whole process.

Meng: For production systems like mine, I’m still thinking about how much overhead it takes to constantly track that associated two seven clause during the search. If you have a lot of clauses, that constant updating sounds like it could be slow in real traffic.

Lalam: The analysis suggests even though they are updating that clause, they manage it efficiently enough so you hit zero Hamming distance with high probability in big O of n squared time.

Tom: So we’re wrapping up on the clustered Sparrow algorithm. It’s basically a way to tackle three seven sat by turning it into a two seven sat problem while keeping the same solution, with polynomial time bounds based on their stochastic local search and Markov chain analysis.

Jane: That's right. The authors are Cristian Dumitrescu from Kitchener, and this work gives us a tangible path toward solving these complex problems with better efficiency than just brute force or simple local search alone. What this implies for the world is that we have a more principled way to tackle NP complete problems by using probability to guide the search. This sets up some interesting questions about how much complexity we can really tame using these kinds of randomized algorithms.

Cristian Dumitrescu

cs.DS

Submitted: 2018-04-30

Updated: 2026-11-16

Comments: 14 pages

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 62/100

The gist: In this paper, we describe an algorithm for 3SAT using stochastic local search to find a 2SAT expression with the same satisfying solution as the original 3SAT expression and present arguments that…

Key concepts

Stochastic Local Search
This is a search technique where the algorithm makes random choices to explore a solution space. In this context, it involves randomly flipping literals in a 3SAT assignment or randomly choosing which 2-clause replaces an unsatisfied 3-clause to guide the search towards a desired structure.
Markov Chain Modeling
The paper models the process of replacing clauses using a two-state Markov chain (positive and null). This mathematical tool helps predict how likely the search is to move from one state to another, providing insights into the algorithm's progress and regression during the search.
Hamming Distance
This metric measures how different two strings are by counting the positions where they differ. In this algorithm, it represents the number of unsatisfied 3-clauses in a current 2SAT expression compared to a target 2SAT expression. A decrease in this distance signifies progress.
Regression Probability
This is the probability that an algorithm's progress reverses, meaning the search moves to a state that is no better than the previous one. The paper analyzes this probability (1/3) to understand how often the search stalls or moves backward during its probabilistic steps.

Terminology

Summary

In this paper, we describe an algorithm for 3SAT using stochastic local search to find a 2SAT expression with the same satisfying solution as the original 3SAT expression and present arguments that this algorithm is polynomial The single most informative sentence about the paper's subject and finding is: We use stochastic local search in order to find a 2SAT expression that has the same satisfying solution as the original 3SAT expression.

Algorithm Description

Schöning’s algorithm for 3SAT involves guessing an initial truth assignment uniformly at random. The core process repeats until the expression is satisfied or rejected, involving a random walk on the boundary of the truth assignment hypercube. p. 1

Where the paper says it

Stop and reject, the expression is not satisfiable. Note that these algorithms involve random walks on the boundary of the truth assignment hypercube (the unit hypercube where each vertex represents a truth assignment).

When a clause is unsatisfied, one of its three literals is flipped with probability one-third. p. 1
Where the paper says it

Let C be some clause not being satisfied by the actual assignment. Pick one of the three literals in the clause at random, and flip its truth value.

The algorithm also maintains an associated 2-CNF expression by randomly choosing one 2-clause from each 3-clause initially. p. 3
Where the paper says it

Guess an initial truth assignment, uniformly at random. Construct the associated 2SAT expression, uniformly at random, by randomly choosing a 2-clause from each 3-clause.

Modeling the Search Process

The process of replacing an associated 2-clause when a corresponding 3-clause is found unsatisfied is modeled with a Markov chain with two states, state 1 (positive) and state 0 (null). The initial probability distribution for this chain is given by p(1) = 2/3 and p(0) = 1/3. p. 2

Where the paper says it

We can model this process with a Markov chain with 2 states, state 1 (corresponding to the positive state) and state 0 (corresponding to the null state). The initial probability distribution is p(1) = 2 3 and p(0) = 1 3 .

The stationary distribution of this Markov chain is found to be pi(1) = 2/3, pi(0) = 1/3. p. 2
Where the paper says it

We also have p(0,0) = 0, p(0,1) = 1 , because in our case we have one null 2-clause and two positive 2-clauses. This Markov chain has stationary distribution 𝜋(1) = 2 3 , 𝜋(0) = 1 3 .

Analyzing Progress and Regression

The Hamming distance between the profile string of the current 2SAT expression and the profile string of the target 2SAT expression represents the number of unsatisfied 3-clauses. The Hamming distance can decrease only when a positive clause is replaced by a null clause, which happens when dealing with a 3-clause that has exactly one true literal under the satisfying assignment. p. 4

Where the paper says it

The Hamming distance to the target 2SAT expression can decrease only when a positive clause is replaced by a null clause in the current 2SAT expression. That can happen only when the 2-clauses involved are related to a 3-clause that has exactly one true literal under the satisfying truth assignment.

The probability of regression is p(REGRESS) = 1/3, while the probability of staying the same is p(STAY) = 1/3. p. 1
Where the paper says it

For example if x has assigned truth value 1 while y and z have truth value 0, then (x ˅ y ) and (x ˅ y) have truth value 1 and (y ˅ z ) has truth value 0. In our example if we choose one of the three 2-clauses uniformly at random, then with probability 2 3 we will choose a positive 2-clause (with truth value 1 under the satisfying truth assignment) and with probability 1 3 we will choose a null 2-clause (with truth value 0 under the satisfying truth assignment).

Complexity and Time Bounds

The authors assume that in time O(m 2), the target 2SAT expression will be found with high probability, where m is the number of clauses in the original 3SAT expression. Since m is a linear function of n, running through the main loop 3n squared times should be sufficient to find a target 2SAT expression and a satisfying truth assignment with high probability. p. 4

Where the paper says it

For the interesting initial 3SAT problems the number of clauses is a linear function in the number of variables m = O(n). So running through the main loop of the algorithm 3 ∙ 𝑛2 times should be sufficient in order to find a target 2SAT expression and a satisfying truth assignment with high probability.

This leads to a conclusion that the algorithm will find a satisfying truth assignment with arbitrarily high probability in biquadratic time O(n 4). p. 4
Where the paper says it

As we mentioned above the 2SATSolver will run in quadratic time O(𝑛2), and we run 3 ∙ 𝑛2 times through the main loop of the algorithm. So, under the unproved assumption above we conclude that our algorithm will find a satisfying truth assignment with arbitrarily high probability in biquadratic time O(𝑛4).

Heuristic Arguments

The analysis relies on the assumption that the conditional probability that the currently associated 2-clause is positive, given that the 3-clause is unsatisfied, is p((A = 1) 3-clause unsatisfied) ≤ 2/3. This assumption suggests that when a clause is unsatisfied, it is more likely to be a null clause. p. 7

Where the paper says it

The algorithm tends to put in the associated 2-CNF expression positive 2-clauses with probability at least 1 2 , and with truth value 1 under the current truth assignment. So when we discover an unsatisfied 3-clause (with all associated 2-clauses unsatisfied), it is likely that the current associated 2-clause is not a positive clause, it is more likely that it is a null clause.

The transition probabilities for the random walk model are given by p(j, j+1) = p(j, j) = p(j, j-1) = 1/3. p. 8
Where the paper says it

p(PROGRESS) = 1 3 . We can model these processes as a random walk with a stay option on the integers with transition probabilities p(j, j+1) = p(j, j) = p(j, j-1) = 1 3 .

This modeling suggests that with arbitrarily high probability in quadratic time O(m 2), the Hamming distance to the target 2SAT expression will be 0. p. 8
Where the paper says it

We can model these processes as a random walk with a stay option on the integers with transition probabilities p(j, j+1) = p(j, j) = p(j, j-1) = 1 3 . With arbitrarily high probability, in quadratic time O(m2 ), the Hamming distance to the target 2SAT expression will be 0, so all 2-clauses in the 2SAT expression will be positive 2-clauses.

Example Walkthrough

An example of the algorithm is presented using a specific 3CNF expression Ψ(x, y, z). The initial assignment is set to x = y = z = 0. p. 5

Where the paper says it

We assume that we chose y and we set y = 1. Now the current truth assignment is x = z = 0, y = 1, and the updated 2-CNF expression is: Φ2(x, y, z) = (y ∨ z) ∧ (ך ∨ ��z) ∧ (ך) ∧ (�� ∨ ��x ∨ ךz) ∧ (ךy ∨ z) ∧ (ךx ∨ y) ∧ (ךy ∨ ךz) (zך ∨ xך) ∧ Now we call the 2SATSolver for 2∙𝑛2 steps, which will report that the associated 2- CNF expression Φ2(x, y, z) is unsatisfiable.

The process involves selecting an associated 2-clause uniformly at random from each 3-clause. p. 2
Where the paper says it

At a certain stage of the algorithm we will have number of unsatisfied 3-clauses. We choose one uniformly at random for replacing the associated 2-clause and flipping the truth value of one of its literals.

Subsequent steps involve replacing the current 2-clause and flipping a literal's truth value based on the outcome of the search. The example demonstrates how the process continues until a satisfying assignment is found or rejected. p. 2
Where the paper says it

3 literals in the 3-clause have truth value 1 then all associated 2-clauses are positive 2- clauses, they have truth value 1 under the satisfying truth assignment. We describe the process of replacing an associated 2-clause, when the corresponding 3-clause is found unsatisfied at a later stage of the algorithm.

References

[Durrett, 2010]. R. Durrett, “Probability; Theory and Examples “, Cambridge University Press, 2010

[Feller, 1968]. W. Feller, “ An Introduction to Probability Theory and Its Applications “, John Wiley & Sons, 1968

[Grinstead, 1997]. C. M. Grinstead,, J. p. 8

Where the paper says it

Feller, “ An Introduction to Probability Theory and Its Applications “, John Wiley & Sons, 1968. [Grinstead, 1997].

L. Snell, “Introduction to Probability“, AMS Publication, 1968

[Hopcroft, 1979]. J. E Hopcroft, J. p. 8

Where the paper says it

Snell, “Introduction to Probability“, AMS Publication, 1968. [Hopcroft, 1979].

D. Ullman “ Introduction to Automata Theory, Languages and Computation “,Addison - Wesley Publishing Company, Inc. p. 8
Where the paper says it

E Hopcroft, J. Ullman “ Introduction to Automata Theory, Languages and Computation “,Addison - Wesley Publishing Company, Inc.

, 1979

[Papadimitriou, 1991]. C.H. Papadimitriou, “On selecting a satisfying truth assignment “, in FOCS, pages 163 – 169, 1991

[Papadimitriou, 1994]. C.H. Papadimitriou, “Computational Complexity “, Addison - Wesley Publishing Company, Inc. p. 8

Where the paper says it

[Papadimitriou, 1994]. Papadimitriou, “Computational Complexity “, Addison - Wesley Publishing Company, Inc.

, 1994

[Schöning, 1991]. Uwe Schöning, “ A probabilistic Algorithm for k-SAT and Constraint Satifaction Problems“, Research Supported by the ESPRIT Basic Research, 1991

[Schöning, 2012]. Uwe Schöning, Adrian Balint, “ Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break “, https://www. p. 9

Where the paper says it

10 [Schöning, 2012]. Uwe Schöning, Adrian Balint, “ Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break“, https://www.

uniulm.de/fileadmin/website uni-ulm/iui. p. 9
Where the paper says it

Uwe Schöning, Adrian Balint, “ Choosing Probability Distributions for Stochastic Local Search and the Role of Make versus Break“, https://www. de/fileadmin/website_uni_ulm/iui.

inst.190/Mitarbeiter/balint/SAT 2012. p. 9
Where the paper says it

de/fileadmin/website_uni_ulm/iui. 190/Mitarbeiter/balint/SAT 2012.

pd

Cristian Dumitrescu, Kitchener, Ontario, Canada

Email: cristiand43@gmail.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved SAT solving capability by using stochastic local search to find a 2SAT expression that has the same satisfying solution as an original 3SAT expression. This allows for finding solutions to NP-complete problems by reducing them to a problem solvable in quadratic time with high probability, rather than relying solely on exponential bounds.

  2. Enhanced efficiency for large instances by employing a Markov chain model (state 1 for positive clause, state 0 for null clause) to analyze the replacement process of associated 2-clauses. This analysis shows that the Hamming distance to the target 2SAT expression can decrease with probability one when processing a type 1 clause, leading to faster convergence.

  3. Biquadratic time complexity for finding a satisfying truth assignment by running the main loop of the algorithm approximately three times n squared iterations, given that each iteration involves a quadratic time 2SATSolver run and an expected polynomial time to find the target 2SAT expression.

Abstract

In this paper, we study an extension of Schoning's algorithm [Schoning, 1991] for 3SAT.

Related papers