Randomised Satisfiability Algorithms

GSAT §

Repeat a specified MAX-TRIES number of times:

1. Select a random interpretation $I$.
2. If $I\models S$ , then return $I$.
3. Repeat a specified MAX-FLIPS number of times:
   1. Select a variable $p$ such that flip(I,p) satisfies the greatest number of clauses in $S$.
   2. Let $I$ = flip(I,p)
   3. If $I\models S$ , then return $I$.
   4. If no model has been found, return "don't know".

If there are multiple candidates for flipping, we select $p$ from the set of candidates using a uniform random function.

GSAT with walks §

Similar to GSAT above, but with the following modifications to step 3.1:

• Follow the same behaviour as GSAT with probability $\pi$,
• With probability $1-\pi$, randomly select $p$ among all variables false in $I$.

Walk Sat (WSAT) §

Similar to GSAT above, but with the following replacement for step 3.1:

• Randomly select a clause $C\in S$ such that $I/\models C$.
• Randomly select variable $p$ from $C$.