Author: Andrew J. Parkes.
To appear in the Workshop "Stochastic Search Algorithms" at the 2001 International Joint Conference on Artificial Intelligence (IJCAI-01)
We consider a simple parallelization, WSAT(PAR), of WSAT in which many flips can be selected and performed in parallel, and independently, using a linear number of processors. On random 3SAT even mildly underconstrained problems can be solved by sequential WSAT in O(n) time (where n is the number of variables per instance). Empirically, we find that in this region WSAT(PAR) takes an average parallel time of O(log(n)2). Hence, not only are such underconstrained problems on average in P, but also appear to be in the much smaller class NC2.