Random walks and Brownian notion

Abstract

Papadimitriou proved in [7] that the random walk algorithm is a  polynomial Monte-Carlo algorithm for the satisfiable instances of 2SAT. We present a convergence criterion that generalizes it. We used it to demonstrate that the random walk algorithm is also a polynomial Monte-Carlo algorithm for the satisfiable Horn-renamable instances of SAT without unitary clauses.