Random walks and Brownian notion
T. Castell
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  
@article{cai608,
     author = {T. Castell},
     title = {Random walks and Brownian notion},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai608}
}

T. Castell. Random walks and Brownian notion. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai608/