Lower bounds for random 3-SAT via differential equations

DOI10.1016/S0304-3975(01)00159-1zbMath0983.68079OpenAlexW2136558174MaRDI QIDQ5958806

Demetrios Achlioptas

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(01)00159-1

zbMATH Keywords

algorithmsdifferential equationsrandom 3-sat

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (30)

Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden ⋮ Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ An algorithm for random signed 3-SAT with intervals ⋮ Phase transitions of PP-complete satisfiability problems ⋮ Phase transition in a random NK landscape model ⋮ Random k -SAT and the power of two choices ⋮ Regular random \(k\)-SAT: Properties of balanced formulas ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ On the thresholds in linear and nonlinear Boolean equations ⋮ Biased random k‐SAT ⋮ The design of novel distributed protocols from differential equations ⋮ The cook-book approach to the differential equation method ⋮ The large deviations of the whitening process in random constraint satisfaction problems ⋮ Satisfiability threshold for power law random 2-SAT in configuration model ⋮ An identity derived from the solution of a class of differential equations for the evolution of a key agreement protocol ⋮ Structure of large random hypergraphs ⋮ 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 ⋮ Destruction of dissipative structures under random actions ⋮ Results related to threshold phenomena research in satisfiability: Lower bounds ⋮ Upper bounds on the satisfiability threshold ⋮ Constructing an asymptotic phase transition in random binary constraint satisfaction problems ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Super solutions of random \((3 + p)\)-SAT ⋮ 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 ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story ⋮ Resolution Complexity of Random Constraint Satisfaction Problems: Another Half of the Story ⋮ Selecting Complementary Pairs of Literals

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A threshold for unsatisfiability
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• The asymptotic number of labeled graphs with given degree sequences
• Differential equations for random processes and random graphs
• 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
• Sharp thresholds of graph properties, and the $k$-sat problem
• Two‐coloring random hypergraphs
• A critical point for random graphs with a given degree sequence
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• Determining computational complexity from characteristic ‘phase transitions’
• Solutions of ordinary differential equations as limits of pure jump markov processes
• The complexity of theorem-proving procedures
• Random constraint satisfaction: A more accurate picture
• Random 2-SAT: Results and problems
• Results related to threshold phenomena research in satisfiability: Lower bounds

This page was built for publication: Lower bounds for random 3-SAT via differential equations