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.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
Issue
Section
Articles