Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
From MaRDI portal
Publication:764375
DOI10.1016/j.tcs.2011.11.014zbMath1280.68237OpenAlexW1997804344MaRDI QIDQ764375
Publication date: 13 March 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2011.11.014
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Near optimal seperation of tree-like and general resolution
- A threshold for unsatisfiability
- Encores on cores
- Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
- When does the giant component bring unsatisfiability?
- Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
- On the complexity of regular resolution and the Davis-Putnam procedure
- A probabilistic analysis of randomly generated binary constraint satisfaction problems.
- Generalized satisfiability problems: Minimal elements and phase transitions.
- The 3-XORSAT threshold.
- Two solutions to diluted \(p\)-spin models and XORSAT problems
- A sharp threshold for a random constraint satisfaction problem
- A sharp threshold in proof complexity yields lower bounds for satisfiability search
- Differential equations for random processes and random graphs
- Sudden emergence of a giant \(k\)-core in a random graph
- Many hard examples in exact phase transitions
- Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
- Generating hard satisfiability problems
- Experimental results on the crossover point in random 3-SAT
- On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
- The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
- Selecting Complementary Pairs of Literals
- Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
- Many hard examples for resolution
- The Resolution Complexity of Random Constraint Satisfaction Problems
- An exponential separation between regular and general resolution
- Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
- Sharp thresholds of graph properties, and the $k$-sat problem
- Short proofs are narrow—resolution made simple
- Models for Random Constraint Satisfaction Problems
- The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
- Analysis of Two Simple Heuristics on a Random Instance ofk-sat
- Cores in random hypergraphs and Boolean formulas
- The complexity of satisfiability problems
- Thek-Core and Branching Processes
- The satisfiability threshold for randomly generated binary constraint satisfaction problems
- Threshold values of random K‐SAT from the cavity method
- Poisson Cloning Model for Random Graphs
- A Computing Procedure for Quantification Theory
- A machine program for theorem-proving
- Principles and Practice of Constraint Programming – CP 2003
- Random constraint satisfaction: A more accurate picture
- Random constraint satisfaction: Flaws and structure
- Rigorous results for random (\(2+p)\)-SAT
- Lower bounds for random 3-SAT via differential equations
- Constructing an asymptotic phase transition in random binary constraint satisfaction problems
This page was built for publication: Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT
