2017/03/06 by Cristian Dumitrescu, Dumitrescu, Cristian
Computer Science · #Constraint Satisfaction and Optimization
paper · pdf · doi:10.48550/arxiv.1703.01905
In this paper I present a 3SAT algorithm based on the randomized algorithm of Papadimitriou from 1991, and Schoning from 1991. We also present strong arguments that this algorithm finds a solution (if it exists) for a 3SAT problem with high probability in polynomial time.