An efficient local search method for random 3-satisfiability

DOI10.1016/S1571-0653(04)00463-9MaRDI QIDQ3439117zbMATH OpenFDO

Authors Sakari Seitz, Pekka Orponen

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S1571-0653(04)00463-9

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• A probabilistic algorithm for k-SAT based on limited local search and restart
• Phase transition for local search on planted SAT
• A deterministic \((2-2/(k+1))^{n}\) algorithm for \(k\)-SAT based on local search.

Cites work

• Coloring random graphs
• Combinatorial landscapes
• Computer search for small complete caps
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Determining computational complexity from characteristic ``phase transitions
• Experimental results on the crossover point in random 3-SAT
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1273988 (Why is no real title available?)
• scientific article; zbMATH DE number 1016966 (Why is no real title available?)
• scientific article; zbMATH DE number 1072538 (Why is no real title available?)
• scientific article; zbMATH DE number 1947423 (Why is no real title available?)
• scientific article; zbMATH DE number 1775444 (Why is no real title available?)
• scientific article; zbMATH DE number 1445295 (Why is no real title available?)
• scientific article; zbMATH DE number 956863 (Why is no real title available?)
• Many hard examples for resolution
• New optimization heuristics. The great deluge algorithm and the record- to-record travel
• On the depth of combinatorial optimization problems
• Optimization by simulated annealing
• Sharp thresholds of graph properties, and the k-sat problem

Cited in

(5)

• An improved local search algorithm for 3-SAT
• Improving configuration checking for satisfiable random \(k\)-SAT instances
• Theory and Applications of Satisfiability Testing
• Theory and Applications of Satisfiability Testing
• Analysis of local search landscapes for \(k\)-SAT instances

Describes a project that uses

Uses Software

• Walksat

This page was built for publication: An efficient local search method for random 3-satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3439117)