title: Complexity of several constraint-satisfaction problems using the heuristic classical algorithm WalkSAT.
abstract: We determine the complexity of several constraint-satisfaction problems using the heuristic algorithm WalkSAT. At large sizes N, the complexity increases exponentially with N in all cases. Perhaps surprisingly, out of all the models studied, the hardest for WalkSAT is the one for which there is a polynomial time algorithm.
authors.affiliation: Dipartimento di Fisica, Università di Ferrara and INFN-Sezione di Ferrara, Ferrara, Italy.
authors.forename: Marco
authors.initials: M
authors.lastname: Guidetti
authors.forename: A P
authors.initials: AP
authors.lastname: Young
mesh_terms: D000465:Algorithms; D003198:Computer Simulation; D008962:Models, Theoretical; D009068:Movement; D010825:Physics / Q000379:methods*; D011789:Quantum Theory; D013269:Stochastic Processes; D013997:Time Factors