Random walks and Brownian notion

Authors

  • T. Castell

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.

Downloads

Download data is not yet available.

How to Cite

Castell, T. (2012). Random walks and Brownian notion. Computing and Informatics, 18(2), 209–214. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/608