Typical case complexity of satisfiability algorithms and the threshold phenomenon (Q2581549): Difference between revisions

@@ Property / DOI @@
-.1016/j.dam.2005.05.008
@@ Property / DOI: 10.1016/j.dam.2005.05.008 / rank @@
-Normal rank
@@ Property / author @@
-John V. Franco
@@ Property / author: John V. Franco / rank @@
-Normal rank
@@ Property / author @@
+John V. Franco
@@ Property / author: John V. Franco / 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.dam.2005.05.008
+Normal rank
@@ Property / OpenAlex ID @@
+W1983259451
@@ Property / OpenAlex ID: W1983259451 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for random 3-SAT via differential equations
+Normal rank
@@ Property / cites work @@
+Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
+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 @@
+Random constraint satisfaction: A more accurate picture
+Normal rank
@@ Property / cites work @@
+The threshold for random k-SAT is 2             <sup>k</sup>             (ln 2 - O(k))
+Normal rank
@@ Property / cites work @@
+Q4542576
@@ Property / cites work: Q4542576 / rank @@
+Normal rank
@@ Property / cites work @@
+Near optimal seperation of tree-like and general resolution
+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
@@ Property / cites work @@
+The scaling window of the 2-SAT transition
@@ Property / cites work: The scaling window of the 2-SAT transition / rank @@
+Normal rank
@@ Property / cites work @@
+A Complexity Index for Satisfiability Problems
@@ Property / cites work: A Complexity Index for Satisfiability Problems / rank @@
+Normal rank
@@ Property / cites work @@
+Recognition of \(q\)-Horn formulae in linear time
@@ Property / cites work: Recognition of \(q\)-Horn formulae in linear time / rank @@
+Normal rank
@@ Property / cites work @@
+Q3140436
@@ Property / cites work: Q3140436 / rank @@
+Normal rank
@@ Property / cites work @@
+Extended Horn sets in propositional logic
@@ Property / cites work: Extended Horn sets in propositional logic / rank @@
+Normal rank
@@ Property / cites work @@
+Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
+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 @@
+Q4012216
@@ Property / cites work: Q4012216 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228436
@@ Property / cites work: Q4228436 / 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 @@
+Q4138187
@@ Property / cites work: Q4138187 / rank @@
+Normal rank
@@ Property / cites work @@
+Generalized satisfiability problems: Minimal elements and phase transitions.
+Normal rank
@@ Property / cites work @@
+Smooth and sharp thresholds for random<i>{k}</i>-XOR-CNF satisfiability
+Normal rank
@@ Property / cites work @@
+Combinatorial sharpness criterion and phase transition classification for random CSPs
+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 @@
+Linear-time algorithms for testing the satisfiability of propositional horn formulae
+Normal rank
@@ Property / cites work @@
+Upper bounds on the satisfiability threshold
@@ Property / cites work: Upper bounds on the satisfiability threshold / rank @@
+Normal rank
@@ Property / cites work @@
+A General Upper Bound for the Satisfiability Threshold of Randomr-SAT Formulae
+Normal rank
@@ Property / cites work @@
+Q4952608
@@ Property / cites work: Q4952608 / rank @@
+Normal rank
@@ Property / cites work @@
+On Random 3-sat
@@ Property / cites work: On Random 3-sat / rank @@
+Normal rank
@@ Property / cites work @@
+Results related to threshold phenomena research in satisfiability: Lower bounds
+Normal rank
@@ Property / cites work @@
+Elimination of Infrequent Variables Improves Average Case Performance of Satisfiability Algorithms
+Normal rank
@@ Property / cites work @@
+Probabilistic performance of a heurisic for the satisfiability problem
+Normal rank
@@ Property / cites work @@
+Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem
+Normal rank
@@ Property / cites work @@
+A perspective on certain polynomial-time solvable classes of satisfiability
+Normal rank
@@ Property / cites work @@
+Sharp thresholds of graph properties, and the $k$-sat problem
+Normal rank
@@ Property / cites work @@
+Analysis of Two Simple Heuristics on a Random Instance ofk-sat
+Normal rank
@@ Property / cites work @@
+On Resolution with Clauses of Bounded Size
@@ Property / cites work: On Resolution with Clauses of Bounded Size / rank @@
+Normal rank
@@ Property / cites work @@
+A threshold for unsatisfiability
@@ Property / cites work: A threshold for unsatisfiability / rank @@
+Normal rank
@@ Property / cites work @@
+Q2762790
@@ Property / cites work: Q2762790 / rank @@
+Normal rank
@@ Property / cites work @@
+Average time analyses of simplified Davis-Putnam procedures
+Normal rank
@@ Property / cites work @@
+The intractability of resolution
@@ Property / cites work: The intractability of resolution / rank @@
+Normal rank
@@ Property / cites work @@
+On Representatives of Subsets
@@ Property / cites work: On Representatives of Subsets / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Tail bounds for occupancy and the satisfiability threshold conjecture
+Normal rank
@@ Property / cites work @@
+Q4411392
@@ Property / cites work: Q4411392 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3597154
@@ Property / cites work: Q3597154 / rank @@
+Normal rank
@@ Property / cites work @@
+Selecting Complementary Pairs of Literals
@@ Property / cites work: Selecting Complementary Pairs of Literals / rank @@
+Normal rank
@@ Property / cites work @@
+Approximating the unsatisfiability threshold of random formulas
+Normal rank
@@ Property / cites work @@
+Q2754130
@@ Property / cites work: Q2754130 / rank @@
+Normal rank
@@ Property / cites work @@
+Investigations on autark assignments
@@ Property / cites work: Investigations on autark assignments / rank @@
+Normal rank
@@ Property / cites work @@
+Renaming a Set of Clauses as a Horn Set
@@ Property / cites work: Renaming a Set of Clauses as a Horn Set / rank @@
+Normal rank
@@ Property / cites work @@
+Determining computational complexity from characteristic ‘phase transitions’
+Normal rank
@@ Property / cites work @@
+The complexity of the matrix eigenproblem
@@ Property / cites work: The complexity of the matrix eigenproblem / rank @@
+Normal rank
@@ Property / cites work @@
+Correction to ``Probabilistic analysis of the Davis Putnam procedure for solving the satisfiability problem''
+Normal rank
@@ Property / cites work @@
+Probe Order Backtracking
@@ Property / cites work: Probe Order Backtracking / rank @@
+Normal rank
@@ Property / cites work @@
+A Machine-Oriented Logic Based on the Resolution Principle
+Normal rank
@@ Property / cites work @@
+On finding solutions for extended Horn formulas
@@ Property / cites work: On finding solutions for extended Horn formulas / rank @@
+Normal rank
@@ Property / cites work @@
+A simplified NP-complete satisfiability problem
@@ Property / cites work: A simplified NP-complete satisfiability problem / rank @@
+Normal rank
@@ Property / cites work @@
+Hard examples for resolution
@@ Property / cites work: Hard examples for resolution / rank @@
+Normal rank
@@ Property / cites work @@
+Differential equations for random processes and random graphs
+Normal rank
@@ Property / DOI @@
+.1016/J.DAM.2005.05.008
@@ Property / DOI: 10.1016/J.DAM.2005.05.008 / rank @@
+Normal rank
@@ links / mardi / name / links / mardi / name @@
+Publication:2581549