Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

DOI10.1016/J.TCS.2011.11.014zbMATH Open1280.68237OpenAlexW1997804344MaRDI QIDQ764375FDOQ764375

Harold Connamacher

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

Recommendations

• Exponential lower bounds for DPLL algorithms on satisfiable random 3-CNF formulas
• Satisfiability threshold for random XOR-CNF formulas
• Exponential bounds for DPLL below the satisfiability threshold
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• Exponential lower bounds for the running time of DPLL algorithms on satisfiable formulas

zbMATH Keywords

algorithmsthresholdDPLLrandom CSP

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Sudden emergence of a giant \(k\)-core in a random graph
• Title not available (Why is that?)
• The complexity of satisfiability problems
• Title not available (Why is that?)
• A Computing Procedure for Quantification Theory
• A machine program for theorem-proving
• Two solutions to diluted \(p\)-spin models and XORSAT problems
• Many hard examples for resolution
• Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
• Critical Behavior in the Satisfiability of Random Boolean Expressions
• Sharp thresholds of graph properties, and the $k$-sat problem
• The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
• Differential equations for random processes and random graphs
• Many hard examples in exact phase transitions
• The Resolution Complexity of Random Constraint Satisfaction Problems
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• Title not available (Why is that?)
• Cores in random hypergraphs and Boolean formulas
• Thek-Core and Branching Processes
• Poisson Cloning Model for Random Graphs
• Random constraint satisfaction: A more accurate picture
• Random constraint satisfaction: Flaws and structure
• Constructing an asymptotic phase transition in random binary constraint satisfaction problems
• Encores on cores
• Short proofs are narrow—resolution made simple
• A probabilistic analysis of randomly generated binary constraint satisfaction problems.
• Generalized satisfiability problems: Minimal elements and phase transitions.
• A sharp threshold for a random constraint satisfaction problem
• Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
• Experimental results on the crossover point in random 3-SAT
• Title not available (Why is that?)
• Analysis of Two Simple Heuristics on a Random Instance ofk-sat
• The satisfiability threshold for randomly generated binary constraint satisfaction problems
• The 3-XORSAT threshold.
• An exponential separation between regular and general resolution
• Selecting Complementary Pairs of Literals
• Lower bounds for random 3-SAT via differential equations
• A threshold for unsatisfiability
• Title not available (Why is that?)
• Threshold values of random K‐SAT from the cavity method
• Near optimal seperation of tree-like and general resolution
• Models for Random Constraint Satisfaction Problems
• Rigorous results for random (\(2+p)\)-SAT
• Random k‐SAT: Two Moments Suffice to Cross a Sharp Threshold
• On the relative complexity of resolution refinements and cutting planes proof systems
• When does the giant component bring unsatisfiability?
• On the complexity of regular resolution and the Davis-Putnam procedure
• Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
• A sharp threshold in proof complexity yields lower bounds for satisfiability search
• Generating hard satisfiability problems
• The phase transition in 1-in-\(k\) SAT and NAE 3-SAT
• The satisfiability threshold for a seemingly intractable random constraint satisfaction problem
• Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms forK-SAT at large clause-to-variable ratios
• Title not available (Why is that?)
• Title not available (Why is that?)
• Principles and Practice of Constraint Programming – CP 2003

Cited In (4)

• Super solutions of random \((3 + p)\)-SAT
• Title not available (Why is that?)
• Satisfiability Thresholds beyond k −XORSAT
• Approximating the Satisfiability Threshold for Random k-XOR-formulas

This page was built for publication: Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q764375)