Lower bounds for random 3-SAT via differential equations
From MaRDI portal
Publication:5958806
DOI10.1016/S0304-3975(01)00159-1zbMath0983.68079OpenAlexW2136558174MaRDI QIDQ5958806
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
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
