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)

Related Items

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

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