Exact thresholds for DPLL on random XOR-SAT and NP-complete extensions of XOR-SAT (Q764375): Difference between revisions

@@ Property / author @@
+Harold S. Connamacher
@@ Property / author: Harold S. Connamacher / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.tcs.2011.11.014
+Normal rank
@@ Property / OpenAlex ID @@
+W1997804344
@@ Property / OpenAlex ID: W1997804344 / rank @@
+Normal rank
@@ Property / cites work @@
+Generating hard satisfiability problems
@@ Property / cites work: Generating hard satisfiability problems / rank @@
+Normal rank
@@ Property / cites work @@
+Random constraint satisfaction: Flaws and structure
+Normal rank
@@ Property / cites work @@
+Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
+Normal rank
@@ Property / cites work @@
+A sharp threshold in proof complexity yields lower bounds for satisfiability search
+Normal rank
@@ Property / cites work @@
+Analysis of Two Simple Heuristics on a Random Instance ofk-sat
+Normal rank
@@ Property / cites work @@
+Rigorous results for random (\(2+p)\)-SAT
@@ Property / cites work: Rigorous results for random (\(2+p)\)-SAT / rank @@
+Normal rank
@@ Property / cites work @@
+The Satisfiability Threshold for a Seemingly Intractable Random Constraint Satisfaction Problem
+Normal rank
@@ Property / cites work @@
+Can rare SAT formulae be easily recognized? On the efficiency of message-passing algorithms for<i>K</i>-SAT at large clause-to-variable ratios
+Normal rank
@@ Property / cites work @@
+On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems
+Normal rank
@@ Property / cites work @@
+Near optimal seperation of tree-like and general resolution
+Normal rank
@@ Property / cites work @@
+An exponential separation between regular and general resolution
+Normal rank
@@ Property / cites work @@
+Q5715680
@@ Property / cites work: Q5715680 / rank @@
+Normal rank
@@ Property / cites work @@
+A Computing Procedure for Quantification Theory
@@ Property / cites work: A Computing Procedure for Quantification Theory / rank @@
+Normal rank
@@ Property / cites work @@
+A machine program for theorem-proving
@@ Property / cites work: A machine program for theorem-proving / rank @@
+Normal rank
@@ Property / cites work @@
+Many hard examples for resolution
@@ Property / cites work: Many hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of regular resolution and the Davis-Putnam procedure
+Normal rank
@@ Property / cites work @@
+Q4228436
@@ Property / cites work: Q4228436 / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold for unsatisfiability
@@ Property / cites work: A threshold for unsatisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Critical Behavior in the Satisfiability of Random Boolean Expressions
+Normal rank
@@ Property / cites work @@
+Experimental results on the crossover point in random 3-SAT
+Normal rank
@@ Property / cites work @@
+Threshold values of random <i>K</i>‐SAT from the cavity method
+Normal rank
@@ Property / cites work @@
+Sharp thresholds of graph properties, and the $k$-sat problem
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
+Normal rank
@@ Property / cites work @@
+The threshold for random 𝑘-SAT is 2^{𝑘}log2-𝑂(𝑘)
+Normal rank
@@ Property / cites work @@
+Selecting Complementary Pairs of Literals
@@ Property / cites work: Selecting Complementary Pairs of Literals / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for random 3-SAT via differential equations
+Normal rank
@@ Property / cites work @@
+Q4704799
@@ Property / cites work: Q4704799 / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of a generalization of the unit-clause literal selection heuristics for the k-satisfiability problem
+Normal rank
@@ Property / cites work @@
+Q3597149
@@ Property / cites work: Q3597149 / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of satisfiability problems
@@ Property / cites work: The complexity of satisfiability problems / rank @@
+Normal rank
@@ Property / cites work @@
+Q2768371
@@ Property / cites work: Q2768371 / rank @@
+Normal rank
@@ Property / cites work @@
+Random <i>k</i>‐SAT: Two Moments Suffice to Cross a Sharp Threshold
+Normal rank
@@ Property / cites work @@
+The 3-XORSAT threshold.
@@ Property / cites work: The 3-XORSAT threshold. / rank @@
+Normal rank
@@ Property / cites work @@
+Two solutions to diluted \(p\)-spin models and XORSAT problems
+Normal rank
@@ Property / cites work @@
+Random constraint satisfaction: A more accurate picture
+Normal rank
@@ Property / cites work @@
+Generalized satisfiability problems: Minimal elements and phase transitions.
+Normal rank
@@ Property / cites work @@
+Principles and Practice of Constraint Programming – CP 2003
+Normal rank
@@ Property / cites work @@
+Models for Random Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+When does the giant component bring unsatisfiability?
+Normal rank
@@ Property / cites work @@
+A probabilistic analysis of randomly generated binary constraint satisfaction problems.
+Normal rank
@@ Property / cites work @@
+The satisfiability threshold for randomly generated binary constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+Constructing an asymptotic phase transition in random binary constraint satisfaction problems
+Normal rank
@@ Property / cites work @@
+Q4954175
@@ Property / cites work: Q4954175 / rank @@
+Normal rank
@@ Property / cites work @@
+Many hard examples in exact phase transitions
@@ Property / cites work: Many hard examples in exact phase transitions / rank @@
+Normal rank
@@ Property / cites work @@
+Random \(k\)-SAT: A tight threshold for moderately growing \(k\)
+Normal rank
@@ Property / cites work @@
+A sharp threshold for a random constraint satisfaction problem
+Normal rank
@@ Property / cites work @@
+The Resolution Complexity of Random Constraint Satisfaction Problems
+Normal rank
@@ Property / cites work @@
+Q4198785
@@ Property / cites work: Q4198785 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3975008
@@ Property / cites work: Q3975008 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3286850
@@ Property / cites work: Q3286850 / rank @@
+Normal rank
@@ Property / cites work @@
+Differential equations for random processes and random graphs
+Normal rank
@@ Property / cites work @@
+Q4519896
@@ Property / cites work: Q4519896 / rank @@
+Normal rank
@@ Property / cites work @@
+Sudden emergence of a giant \(k\)-core in a random graph
+Normal rank
@@ Property / cites work @@
+Cores in random hypergraphs and Boolean formulas
@@ Property / cites work: Cores in random hypergraphs and Boolean formulas / rank @@
+Normal rank
@@ Property / cites work @@
+Encores on cores
@@ Property / cites work: Encores on cores / rank @@
+Normal rank
@@ Property / cites work @@
+Poisson Cloning Model for Random Graphs
@@ Property / cites work: Poisson Cloning Model for Random Graphs / rank @@
+Normal rank
@@ Property / cites work @@
+The<i>k</i>-Core and Branching Processes
@@ Property / cites work: The<i>k</i>-Core and Branching Processes / rank @@
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank