Solving non-uniform planted and filtered random SAT formulas greedily
type: Item
instance of: scholarly article
title: Solving non-uniform planted and filtered random SAT formulas greedily
DOI: 10.1007/978-3-030-80223-3_13
author: Tobias Friedrich
author: F. Neumann
author: Ralf Rothenberger
author: Andrew M. Sutton
publication date: 2022-03-22T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R07
Mathematics Subject Classification ID: 68T20
zbMATH DE Number: 7495573
zbMATH Keywords: random \(k\)-SAT
zbMATH Keywords: planted \(k\)-SAT
zbMATH Keywords: non-uniform variable distribution
zbMATH Keywords: greedy algorithm
zbMATH Keywords: local search
describes a project that uses: CPSparrow
describes a project that uses: gluHack
MaRDI profile type: Publication
full work available at URL: 978-3-030-80223-3 13
OpenAlex ID: W3186343225
cites work: Q5715725
cites work: Rigorous results for random (\(2+p)\)-SAT
cites work: The Fractal Dimension of SAT Formulas
cites work: Optimal testing for planted satisfiability problems
cites work: Regular random \(k\)-SAT: Properties of balanced formulas
cites work: On Sharp Thresholds in Random Geometric Graphs
cites work: Phase Transition for Local Search on Planted SAT
cites work: Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
cites work: Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
cites work: Q4228436
cites work: Many hard examples for resolution
cites work: The Number of Satisfying Assignments of Random Regulark-SAT Formulas
cites work: Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
cites work: Q3191589
cites work: On the Complexity of Random Satisfiability Problems with Planted Solutions
cites work: A spectral technique for random satisfiable 3CNF formulas
cites work: Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
cites work: Sharp thresholds of graph properties, and the $k$-sat problem
cites work: Q5111724
cites work: Generating SAT instances with community structure
cites work: On the greedy algorithm for satisfiability
cites work: Solving random satisfiable 3CNF formulas in expected polynomial time
cites work: Satisfiability threshold for power law random 2-SAT in configuration model
cites work: Bounds on Threshold of Regular Random k-SAT
cites work: Critical behavior in the computational cost of satisfiability testing
description: scientific article; zbMATH DE number 7495573