Lower bounds for random 3-SAT via differential equations
From MaRDI portal
Publication:5958806
DOI10.1016/S0304-3975(01)00159-1zbMath0983.68079MaRDI 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
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
Related Items
An identity derived from the solution of a class of differential equations for the evolution of a key agreement protocol, Biased landscapes for random constraint satisfaction problems, Kolmogorov complexity based upper bounds for the unsatisfiability threshold of random k-SAT, Satisfiability threshold for power law random 2-SAT in configuration model, 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, Biased measures for random constraint satisfaction problems: larger interaction range and asymptotic expansion, Generating Random SAT Instances: Multiple Solutions could be Predefined and Deeply Hidden, Biased random k‐SAT, The cook-book approach to the differential equation method, Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances, On the thresholds in linear and nonlinear Boolean equations, Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT, Regular random \(k\)-SAT: Properties of balanced formulas, 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, A sharp threshold in proof complexity yields lower bounds for satisfiability search, The design of novel distributed protocols from differential equations, Destruction of dissipative structures under random actions, Super solutions of random \((3 + p)\)-SAT, Phase transition in a random NK landscape model, Typical case complexity of satisfiability algorithms and the threshold phenomenon, Resolution complexity of random constraint satisfaction problems: Another half of the story, An algorithm for random signed 3-SAT with intervals, Phase transitions of PP-complete satisfiability problems, Random k -SAT and the power of two choices, The large deviations of the whitening process in random constraint satisfaction problems, 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
