Rigorous results for random (\(2+p)\)-SAT
From MaRDI portal
Publication:5958803
DOI10.1016/S0304-3975(01)00154-2zbMath0992.68073WikidataQ126588251 ScholiaQ126588251MaRDI QIDQ5958803
Danny Krizanc, Evangelos Kranakis, Lefteris M. Kirousis, Demetrios Achlioptas
Publication date: 3 March 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items
GD-SAT model and crossover line ⋮ Many hard examples in exact phase transitions ⋮ A sharp threshold in proof complexity yields lower bounds for satisfiability search ⋮ The state of SAT ⋮ Heuristic average-case analysis of the backtrack resolution of random 3-satisfiability instances ⋮ On the thresholds in linear and nonlinear Boolean equations ⋮ $(2+\varepsilon)$-Sat Is NP-hard ⋮ Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities ⋮ On the average similarity degree between solutions of random \(k\)-SAT and random CSPs. ⋮ On the Lower Bounds of (1,0)-Super Solutions for Random k-SAT ⋮ A NEW UPPER BOUND FOR RANDOM (2 + p)-SAT BY FLIPPING TWO VARIABLES ⋮ 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 ⋮ Unnamed Item ⋮ Statistical and algebraic analysis of a family of random Boolean equations ⋮ Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT ⋮ Super solutions of random \((3 + p)\)-SAT ⋮ Typical case complexity of satisfiability algorithms and the threshold phenomenon ⋮ Resolution complexity of random constraint satisfaction problems: Another half of the story ⋮ Solving non-uniform planted and filtered random SAT formulas greedily
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- Differential equations for random processes and random graphs
- 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
- Approximating the unsatisfiability threshold of random formulas
- Sharp thresholds of graph properties, and the $k$-sat problem
- On a Correlation Inequality of Farr
- A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
- Entropy of theK-Satisfiability Problem
- Bounding the unsatisfiability threshold of random 3-SAT
- Tail bounds for occupancy and the satisfiability threshold conjecture
- On Random 3-sat
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Tricritical points in random combinatorics: the -SAT case
- Determining computational complexity from characteristic ‘phase transitions’
- 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
- Random 2-SAT: Results and problems
