Abstract
Relaxation and..... A study was conducted on the dynamics of a simple search procedure for the satisfaction of Boolean constraints, the RandomWalkSAT algorithm. It was shown using complementary techniques that, for randmly drawn input instances, RandomWalkSAT may have two qualitatively distinct behaviors. Instances with small ratios α of clauses pervariable were almost surely solved in a time growing linearly with their size.
| Original language | English |
|---|---|
| Article number | 066103 |
| Pages (from-to) | 066103/1-066103/18 |
| Journal | Physical Review E |
| Volume | 67 |
| Issue number | 6 2 |
| Publication status | Published - 1 Jun 2003 |
| Externally published | Yes |