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