Experimental results are given on the scaling of the Pure Random Walk version (PRWSAT) of WalkSAT. PRWSAT is very simple because of the absence of heuristics: not only the clause is selected at random, but also the literal within that clause. The main result is that, despite the simplicity and absence of heuristics, it has non-trivial behavior on Random 3-SAT. There appears to be a threshold at a clause/variable ratio of about 2.65. Below the threshold, problems are solved in a tightly-distributed and linear number of flips. Above the threshold scaling appears to be non-polynomial. The simplicity and the nontrivial threshold make it a good candidate for theoretical analysis.
© Springer-Verlag
To appear in proceedings of CP2002, that will be published in the LNCS series.