Solving non-uniform planted and filtered random SAT formulas greedily

DOI10.1007/978-3-030-80223-3_13OpenAlexW3186343225MaRDI QIDQ2118298

Tobias Friedrich, Frank Neumann, Andrew M. Sutton, Ralf Rothenberger

Publication date: 22 March 2022

Full work available at URL: https://doi.org/10.1007/978-3-030-80223-3_13

zbMATH Keywords

greedy algorithmlocal searchrandom \(k\)-SATnon-uniform variable distributionplanted \(k\)-SAT

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational aspects of satisfiability (68R07)

Uses Software

• CPSparrow
• gluHack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Generating SAT instances with community structure
• Regular random \(k\)-SAT: Properties of balanced formulas
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• On the greedy algorithm for satisfiability
• Optimal testing for planted satisfiability problems
• Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
• Critical behavior in the computational cost of satisfiability testing
• Phase Transition for Local Search on Planted SAT
• On Sharp Thresholds in Random Geometric Graphs
• The Number of Satisfying Assignments of Random Regulark-SAT Formulas
• The Fractal Dimension of SAT Formulas
• Many hard examples for resolution
• A spectral technique for random satisfiable 3CNF formulas
• Solving random satisfiable 3CNF formulas in expected polynomial time
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Sharp thresholds of graph properties, and the $k$-sat problem
• On the Complexity of Random Satisfiability Problems with Planted Solutions
• Bounds on Threshold of Regular Random k-SAT
• Satisfiability threshold for power law random 2-SAT in configuration model
• Rigorous results for random (\(2+p)\)-SAT

This page was built for publication: Solving non-uniform planted and filtered random SAT formulas greedily