Rigorous results for random (\(2+p)\)-SAT

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)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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