Results related to threshold phenomena research in satisfiability: Lower bounds

DOI10.1016/S0304-3975(01)00158-XzbMath0983.68081WikidataQ126527927 ScholiaQ126527927MaRDI QIDQ5958805

John V. Franco

Publication date: 3 March 2002

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

zbMATH Keywords

phase transitionsatisfiability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Average time analyses of simplified Davis-Putnam procedures
• Probabilistic performance of a heurisic for the satisfiability problem
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• Phase transitions and the search problem
• Generating hard satisfiability problems
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
• Sharp thresholds of graph properties, and the $k$-sat problem
• Probe Order Backtracking
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• A Machine-Oriented Logic Based on the Resolution Principle
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• The complexity of theorem-proving procedures
• Random constraint satisfaction: A more accurate picture
• Lower bounds for random 3-SAT via differential equations

Related Items (13)

A Model for Phase Transition of Random Answer-Set Programs ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ Resolving Braess's paradox in random networks ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ On the freezing of variables in random constraint satisfaction problems ⋮ Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT ⋮ Lower bounds for random 3-SAT via differential equations ⋮ Upper bounds on the satisfiability threshold ⋮ Constructing an asymptotic phase transition in random binary constraint satisfaction problems ⋮ Phase transition of multivariate polynomial systems ⋮ Biased landscapes for random constraint satisfaction problems ⋮ Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon

This page was built for publication: Results related to threshold phenomena research in satisfiability: Lower bounds