On the satisfiability threshold of formulas with three literals per clause

DOI10.1016/j.tcs.2009.02.020zbMath1173.68025OpenAlexW2006474266WikidataQ57991449 ScholiaQ57991449MaRDI QIDQ2271431

Lefteris M. Kirousis, Josep Diaz, Dieter Mitsche, Xavier Pérez-Giménez

Publication date: 7 August 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.02.020

Mathematics Subject Classification ID

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

Related Items (14)

Satisfiability Thresholds beyond k −XORSAT ⋮ A general model and thresholds for random constraint satisfaction problems ⋮ Treewidth of Erdős-Rényi random graphs, random intersection graphs, and scale-free random graphs ⋮ The cook-book approach to the differential equation method ⋮ On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES ⋮ Branching Process Approach for 2-Sat Thresholds ⋮ Unnamed Item ⋮ New models for generating hard random Boolean formulas and disjunctive logic programs ⋮ Unnamed Item ⋮ Estimating satisfiability ⋮ Super solutions of random \((3 + p)\)-SAT ⋮ A model of random industrial SAT

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
• Random MAX SAT, random MAX CUT, and their phase transitions
• Tail bounds for occupancy and the satisfiability threshold conjecture
• The probabilistic analysis of a greedy satisfiability algorithm
• On the solution-space geometry of random constraint satisfaction problems
• Upper bounds on the satisfiability threshold

This page was built for publication: On the satisfiability threshold of formulas with three literals per clause